pid=5654">【HDOJ 5654】 xiaoxin and his watermelon candy（离线+树状数组）
xiaoxin and his watermelon candy
Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 233 Accepted Submission(s): 61
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
T(T≤10)
which represents the number of test cases.
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
n
integer 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].
1
5
1 2 3 4 5
3
1 3
1 4
1 5
1
2
3
pid=5648" target="_blank">5648
pid=5646" target="_blank">5646
5645题目大意:有n个糖果。从左到右列出每一个糖果的甜度
之后有Q次查询，每次查询[L,R]中三元组的个数
这个三元组要求满足为连续的三个值，然后这三个值为非递减。
问[L,R]中不反复的三元组的个数。
反复表示三元组中三个数均对影响等。
假设反复则仅仅记一次
正解为主席树………………额………………恩…………
搜到这个离线+树状数组的写法，给大家分享下
思路非常巧妙。先离线存储全部查询。
然后对查询进行排序，以右边界从小到大排序。
然后从1到n開始枚举位置pos
每到一个位置，看一下从当前往后连续的三个满不满足题目中三元组的要求，假设满足。在树状数组中1的位置+1 pos+1处-1
如今让我们先不考虑反复。
经过如上处理，对于全部右边界等于pos+2的区间，树状数组中0~L的值即为三元组个数！
由于假设满足R等于pos+2 事实上就是找全部出现过的l >= L的三元组，在遍历的过程中。每一个满足要求的三元组pos+1处-1了，事实上就是求0~L的区间和了
想想看～～
至于R 等于pos+2 因为对查询依照R排序了，所以在遍历的过程中对于每一个pos都把查询遍历到右区间pos+2就好啦
这里没有去重，关于去重。我是琢磨了好久……做法就是哈希，哈希三元组。
假设没出现过。跟上面一样，在线段树1处+1
假设出现过，须要在上次出现的位置+1处 累加上一个1
这样就能够避免反复统计了
做这道题真长记性……因为要哈希，排序必须对全部元素都进行比較。
否则会出现重叠！
这也是跟其内部实现相关。
代码例如以下:
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout) using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8; int bit[233333];
int n; int Lowbit(int x)
{
return x&(-x);
} int sum(int x)
{
int ans = 0;
while(x)
{
ans += bit[x];
x -= Lowbit(x);
}
return ans;
} void add(int x,int d)
{
while(x <= n)
{
bit[x] += d;
x += Lowbit(x);
}
} struct Point
{
int l,r,id;
bool operator <(const struct Point a)const
{
return r == a.r? l == a.l? id < a.id: l < a.l: r < a.r;
}
Point(int _l = 0,int _r = 0,int _id = 0):l(_l),r(_r),id(_id){};
}; Point pt[233333];
int num[233333];
int ans[233333];
int p[233333]; int main()
{
int t,m; scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 1; i <= n; ++i)
scanf("%d",&num[i]);
scanf("%d",&m);
for(int i = 0; i < m; ++i)
{
scanf("%d%d",&pt[i].l,&pt[i].r);
pt[i].id = i;
} memset(ans,0,sizeof(ans));
memset(bit,0,sizeof(bit));
sort(pt,pt+m); map <Point,int> mp;
int j = 0;
int tp = 1;
for(int i = 1; i <= n-2; ++i)
{
if(num[i] <= num[i+1] && num[i+1] <= num[i+2])
{
if(!mp[Point(num[i],num[i+1],num[i+2])])
{
mp[Point(num[i],num[i+1],num[i+2])] = tp;
p[tp++] = 0;
}
int x = mp[Point(num[i],num[i+1],num[i+2])];
add(p[x]+1,1);
add(i+1,-1);
p[x] = i;
}
for(; j < m && pt[j].r <= i+2; ++j)
{
if(pt[j].l+2 > pt[j].r) continue;
ans[pt[j].id] = sum(pt[j].l);
}
} for(int i = 0; i < m; ++i)
printf("%d\n",ans[i]);
} return 0;
}