pid=5654">【HDOJ 5654】 xiaoxin and his watermelon candy（离线+树状数组）

xiaoxin and his watermelon candy

1
5
1 2 3 4 5
3
1 3
1 4
1 5

1
2
3

题目大意:有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;
}