程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj2821 作詩(Poetize)

bzoj2821 作詩(Poetize)

編輯:C++入門知識

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

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

Sample Output

2
0
0
0
1

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);
	}
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved