首页 > 代码库 > BZOJ 2821 作诗
BZOJ 2821 作诗
类似上题的做法,f[i][j]表示第i块到第j块出现偶数次的数有多少个,然后调整一下。
复杂度n√nlogn。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define maxn 100050 using namespace std; int n,c,m,a[maxn],cnt[maxn],blo[maxn],ret=0,f[2050][2050],l,r,len,st[maxn],lastans=0; int flag[maxn],base[maxn],times=0; int l1,r1,l2,r2,s[maxn],s1[maxn],s2[maxn],top=0; vector <int> v[maxn]; int read() { char ch;int data=http://www.mamicode.com/0; while (ch<‘0‘ || ch>‘9‘) ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘) { data=data*10+ch-‘0‘; ch=getchar(); } return data; } void build() { ret=1; for (int i=1;i<=n;i++) { blo[i]=ret;v[a[i]].push_back(i); if (!(i%len) && i!=n) {st[ret]=i;ret++;} } if (n%len) st[ret]=n; for (int i=1;i<=ret;i++) { int t1=0,t2=0;memset(cnt,0,sizeof(cnt)); for (int j=(i-1)*len+1;j<=n;j++) { cnt[a[j]]++; if (cnt[a[j]]==1) t2++; else if (cnt[a[j]]&1) t1--,t2++; else t1++,t2--; if (!(j%len)) f[i][j/len]=t1; } if (n%len) f[i][ret]=t1; } } int find_(int l,int r,int x) { int ans1=-1,ans2=-1,left,right; left=0;right=v[x].size()-1; while (left<=right) { int mid=(left+right)>>1; if (v[x][mid]>=l) {ans1=mid;right=mid-1;} else left=mid+1; } left=0;right=v[x].size()-1; while (left<=right) { int mid=(left+right)>>1; if (v[x][mid]<=r) {ans2=mid;left=mid+1;} else right=mid-1; } if ((ans1==-1) || (ans2==-1)) return 0; return ans2-ans1+1; } int ask(int l,int r) { times++; if (blo[l]+1>blo[r]-1) { int t1=0,t2=0; for (int i=l;i<=r;i++) { if (flag[a[i]]!=times) {flag[a[i]]=times;t2++;base[a[i]]=cnt[a[i]];cnt[a[i]]++;} else { cnt[a[i]]++; if ((cnt[a[i]]-base[a[i]])&1) t1--,t2++; else t1++,t2--; } } return t1; } else { top=0;l1=l;r1=r;l2=st[blo[l]]+1;r2=st[blo[r]-1];int ret=f[blo[l]+1][blo[r]-1]; for (int i=l;i<=st[blo[l]];i++) s[++top]=a[i]; for (int i=st[blo[r]-1]+1;i<=r;i++) s[++top]=a[i]; sort(s+1,s+top+1);top=unique(s+1,s+top+1)-s-1; for (int i=1;i<=top;i++) s1[i]=find_(l1,r1,s[i]),s2[i]=find_(l2,r2,s[i]); for (int i=1;i<=top;i++) { if (!s2[i]) { if (s1[i]&1) continue; ret++; } else { if ((s2[i]&1) && (!(s1[i]&1))) ret++; if ((!(s2[i]&1)) && (s1[i]&1)) ret--; } } return ret; } } int main() { n=read();c=read();m=read();len=80; for (int i=1;i<=n;i++) a[i]=read(); build(); for (int i=1;i<=m;i++) { l=read();r=read(); l=(l+lastans)%n+1;r=(r+lastans)%n+1; if (l>r) swap(l,r); lastans=ask(l,r);printf("%d\n",lastans); } return 0; }
BZOJ 2821 作诗
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。