HDU 5654 xiaoxin and his watermelon candy 离线树状数组
xiaoxin and his watermelon candy
xiaoxin is very smart since he was a child. He arrange these candies in a line and at each time before eating candies, he selects three continuous watermelon candies from a specific range [L, R] to eat and the chosen triplet must satisfies:
if he chooses a triplet (ai,aj,ak) then:
1. j=i+1,k=j+1
2. ai≤aj≤ak
Your task is to calculate how many different ways xiaoxin can choose a triplet in range [L, R]?
two triplets (a0,a1,a2) and (b0,b1,b2) are thought as different if and only if:
a0≠b0 or a1≠b1 or a2≠b2
For each test case, the first line contains a single integer n(1≤n≤200,000)which represents number of watermelon candies and the following line contains ninteger numbers which are given in the order same with xiaoxin arranged them from left to right.
The third line is an integer Q(1≤200,000) which is the number of queries. In the following Q lines, each line contains two space seperated integers l,r(1≤l≤r≤n) which represents the range [l, r].
5
1 2 3 4 5
3
1 3
1 4
1 5
2
3
#pragma comment(linker, "/STACK:10240000,10240000")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<map>
using namespace std;
const int N = 1e6+, M = , mod = 1e9+, inf = 0x3f3f3f3f;
typedef long long ll;
//不同为1,相同为0 map< pair< int, pair< int,int> > ,int> mp;
int T,a[N],n,m,b[N],c,C[N],nex[N],p[N],H[N];
struct data{int l,r,id,ans;}Q[N];
int cmp1(data a,data b) {if(a.l==b.l) return a.r<b.r;else return a.l<b.l;}
int cmp2(data a,data b) {return a.id<b.id;}
int lowbit(int x) {
return x&(-x);
}
void add(int x, int add) {
for (; x <= n; x += lowbit(x)) {
C[x] += add;
}
}
int sum(int x) {
int s = ;
for (; x > ; x -= lowbit(x)) {
s += C[x];
}
return s;
}
int main() {
scanf("%d",&T);
while(T--) {
mp.clear();
memset(H,,sizeof(H));
memset(p,,sizeof(p));
memset(b,-,sizeof(b));
memset(C,,sizeof(C));memset(nex,,sizeof(nex));
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]), b[i] = -,nex[i] = ;
int k = ;
for(int i=;i<=n;i++) {
if(a[i]>=a[i-]&&a[i-]>=a[i-]) {
if(mp[make_pair(a[i-],make_pair(a[i-],a[i]))]) b[i] = mp[make_pair(a[i-],make_pair(a[i-],a[i]))];
else b[i] = k,mp[make_pair(a[i-],make_pair(a[i-],a[i]))] = k,H[k] = , k++;
}
else b[i] = -;
}
for(int i=n;i>=;i--)
if(b[i]!=-)
nex[i]=p[b[i]],p[b[i]]=i;
for(int i=;i<k;i++)
add(p[i],);
int q;
scanf("%d",&q);
for(int i=;i<=q;i++) {
scanf("%d%d",&Q[i].l,&Q[i].r);Q[i].id = i;
}
sort(Q+,Q+q+,cmp1);
int l = ;
for(int i=;i<=q;i++) {
while(l<Q[i].l+) {
if(nex[l] ) add(nex[l],);l++;
}
if(Q[i].l+>Q[i].r) Q[i].ans = ;
else Q[i].ans = sum(Q[i].r) - sum(Q[i].l+-);
}
sort(Q+,Q+q+,cmp2);
for(int i=;i<=q;i++) {
printf("%d\n",Q[i].ans);
}
}
return ;
}
最新文章
- 通过命令行连接Wifi
- 创建线程方式-NSOperation
- css的引入方法2
- HTML的表格标签
- 【转】NSString属性什么时候用copy,什么时候用strong?
- mysql报错Table &#39;.\erchina_news\v9_search&#39; is marked as crashed and should be repaired
- linux笔记2.21
- 标准I/O介绍
- Singal Page App:使用Knockout和RequireJS创建高度模块化的单页应用引擎
- List与Linkedlist、Arrylist、Vector、Map应用
- Java+Velocity模板引擎集成插件到Eclipse及使用例子
- 关于oracle视图小结
- Nginx 在线新增模块
- Hadoop EC 踩坑 :data block 缺失导致的 HDFS 传输速率下降
- Python3学习笔记17-类与实例
- aircrack-ng后台跑包, 成功后自动发送邮件通知
- 力扣(LeetCode) 509. 斐波那契数
- C++连接mysql及遇到的相关问题
- POST、GET请求中文参数乱码问题
- 7 切片slice
热门文章
- Hdu-5983 2016ACM/ICPC亚洲区青岛站 B.Pocket Cube 模拟
- resgen.exe 已退出 代码为 1073741701的错误的解决办法
- javascript的基础知识及面向对象和原型属性
- mybatis学习笔记之基础复习(3)
- 移动端H5 判断IOS还是Android 平台
- nginx配置和测试
- sql_1
- utf8_general_ci、utf8_unicode_ci和utf8_bin的区别(转载)
- 仅前端cookie之记住密码
- 可横向滑动的vue tab组件