HDU5286 – wyh2000 and sequence(分块)

传送门：HDU5286

【题意】点击中文题意

【分析】以前一直用各个区间可以加加减减的分块，导致我一直往区间加减想，始终想不出，看了别人代码后，原来可以用N*sqrt(N)复杂度来预处理块x~y之间的答案，而这题又是只能通过往块中一个一个加入才能算出答案，所以枚举每个块作为起点到最后一个块一个一个加入来预处理ret[x][y]，插入一个值p递推公式为，ans = (ans-p^cnt[p]+p^(cnt[p]+1))这样复杂度是N*sqrt(N)；然后对于查询区间[l,r],则中间块直接是答案ret[x][y],把左右两端点的不完整块一个一个加入进入就好了，具体看代码。

写着写着停电了，郁闷，就这样吧。

【AC CODE】1388ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 50000+10, SIZE = 200,SN = MAXN/SIZE+2, MOD = 1000000007;//SIZE-每一块的大小
int n,a[MAXN],sot[MAXN],num[MAXN];//离散
int sn,ret[SN][SN],c[SN][MAXN],sum[MAXN];
//sn-块数,ret[x][y]-块x~y的所有答案,c[x][i]-第0~k块中a[i]出现的次数
vector<LL> sqr[MAXN];//x[i]^b,b>=1

void init()
{
	rep(i,0,n) sqr[i].clear(),sqr[i].push_back(0);
	rep(i,0,n)
	{
		LL tmp;
		if(1 == sqr[num[i]].size()) tmp = a[i];
		else tmp = sqr[num[i]][sqr[num[i]].size()-1]*a[i]%MOD;
		sqr[num[i]].push_back(tmp);
	}
	sn = n/SIZE+bool(n%SIZE);
	rep(i,0,sn)
	{
		clc(sum,0);
		int tmp = 0;
		rep(j,i*SIZE,n)
		{
			tmp = (tmp-sqr[num[j]][sum[num[j]]]+sqr[num[j]][sum[num[j]]+1]+MOD)%MOD;
			ret[i][j/SIZE] = tmp;
			sum[num[j]]++;
		}
	}
	clc(c,0);
	rep(i,0,sn)
	{
		if(i) memcpy(c[i],c[i-1],sizeof(c[i]));
		for(int j = 0; j < SIZE && j+i*SIZE < n;j++)
			c[i][num[i*SIZE+j]]++;
	}
	clc(sum,0);
}
int p[SIZE<<1];
int query(int x, int y)
{
	int ans = 0,cnt = 0;
	int st = x/SIZE,ed = y/SIZE;
	if(st < ed)
	{
		per(i,SIZE*(st+1)-1,x) p[cnt++] = num[i];
		repe(i,SIZE*ed,y) p[cnt++] = num[i];
		if(st+1 < ed) ans = ret[st+1][ed-1];
	}
	else repe(i,x,y) p[cnt++] = num[i];
	rep(i,0,cnt)
	{
		if(!sum[p[i]] && st+1 < ed) sum[p[i]] = c[ed-1][p[i]]-c[st][p[i]];
		ans = (ans-sqr[p[i]][sum[p[i]]]+sqr[p[i]][sum[p[i]]+1]+MOD)%MOD;
		sum[p[i]]++;
	}
	rep(i,0,cnt) sum[p[i]] = 0;
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int q;
		scanf("%d %d", &n, &q);
		rep(i,0,n)
		{
			scanf("%d", &a[i]);
			sot[i] = a[i];
		}
		sort(sot,sot+n);
		int cnt = unique(sot,sot+n)-sot;
		rep(i,0,n) num[i] = lower_bound(sot,sot+cnt,a[i])-sot;
		init();
		int la = 0;
		while(q--)
		{
			int a,b;
			scanf("%d %d", &a, &b);
			int x = min((a^la)%n,(b^la)%n),y = max((a^la)%n,(b^la)%n);
			la = query(x,y);
			printf("%d\n", la);
		}
	}
	return 0;
}