bzoj2821 作詩(Poetize)

bzoj2821 作詩(Poetize)

Description

神犇SJY虐完HEOI之後給傻×LYD出了一題：
SHY是T國的公主，平時的一大愛好是作詩。
由於時間緊迫，SHY作完詩之後還要虐OI，於是SHY找來一篇長度為N的文章，閱讀M次，每次只閱讀其中連續的一段[l,r]，從這一段中選出一些漢字構成詩。因為SHY喜歡對偶，所以SHY規定最後選出的每個漢字都必須在[l,r]裡出現了正偶數次。而且SHY認為選出的漢字的種類數（兩個一樣的漢字稱為同一種）越多越好（為了拿到更多的素材！）。於是SHY請LYD安排選法。
LYD這種傻×當然不會了，於是向你請教……
問題簡述：N個數，M組詢問，每次問[l,r]中有多少個數出現正偶數次。

Input

輸入第一行三個整數n、c以及m。表示文章字數、漢字的種類數、要選擇M次。
第二行有n個整數，每個數Ai在[1, c]間，代表一個編碼為Ai的漢字。
接下來m行每行兩個整數l和r，設上一個詢問的答案為ans(第一個詢問時ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交換L和R，則本次詢問為[L,R]。

Output

輸出共m行，每行一個整數，第i個數表示SHY第i次能選出的漢字的最多種類數。

Sample Input

Sample Output

HINT

對於100%的數據，1<=n,c,m<=10^5
 

Source

By lydrainbowcat

很神奇的分塊題！！！

為什麼說它神奇呢？因為我的程序在本機過了，26s，然而交到網站上就TLE了......並不知道為什麼(大概RP不好吧)，希望有好心的小伙伴幫我看看，謝謝啦！！

這道題是強制在線的。我們將整個序列分塊，然後預處理兩個量：s[i][j]表示第i種漢字在前j塊中的出現次數，ans[i][j]表示第i塊到第j塊出現偶數次的漢字的數目。

對於每個詢問，先將整塊的ans[i][j]加到答案中，再把多余部分統計一遍數目，和塊內的進行比較，並對答案做出調整。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
using namespace std;
int n,m,c,block,num,pre=0,l,r;
int a[maxn],ans[320][320],s[320][maxn],pos[maxn],f[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();c=read();m=read();
	F(i,1,n) a[i]=read();
	block=int(sqrt(n));num=n/block;
	F(i,1,n) pos[i]=(i-1)/block+1;
	F(i,1,num)
	{
		int cnt=0;
		memset(f,0,sizeof(f));
		F(j,(i-1)*block+1,n)
		{
			f[a[j]]++;
			if (!(f[a[j]]&1)) cnt++;
			else if (f[a[j]]>2) cnt--;
			if (j%block==0) ans[i][j/block]=cnt;
		}
	}
	F(i,1,n) s[pos[i]][a[i]]++;
	F(i,2,num) F(j,1,c) s[i][j]+=s[i-1][j];
	F(i,1,m)
	{
		int x=read(),y=read();
		l=(x+pre)%n+1;r=(y+pre)%n+1;
		if (l>r) swap(l,r);
		int pl=pos[l],pr=pos[r];
		pre=0;
		memset(f,0,sizeof(f));
		if (pl==pr)
		{
			F(j,l,r)
			{
				f[a[j]]++;
				if ((f[a[j]]&1)&&f[a[j]]>2) pre--;
				if (!(f[a[j]]&1)) pre++;
			}
		}
		else
		{
			pre=ans[pl+1][pr-1];
			F(j,l,pl*block)
			{
				f[a[j]]++;
				int tmp=s[pr-1][a[j]]-s[pl][a[j]];
				if (tmp&1){if (f[a[j]]&1) pre++;else pre--;}
				else if (tmp){if (f[a[j]]&1) pre--;else pre++;}
				else{if ((f[a[j]]&1)&&f[a[j]]>2) pre--;if (!(f[a[j]]&1)) pre++;}
			}
			F(j,(pr-1)*block+1,r)
			{
				f[a[j]]++;
				int tmp=s[pr-1][a[j]]-s[pl][a[j]];
				if (tmp&1){if (f[a[j]]&1) pre++;else pre--;}
				else if (tmp){if (f[a[j]]&1) pre--;else pre++;}
				else{if ((f[a[j]]&1)&&f[a[j]]>2) pre--;if (!(f[a[j]]&1)) pre++;}
			}
		}
		printf("%d\n",pre);
	}
}