2821: 作诗(Poetize)
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 2200 Solved: 614
[Submit][Status][Discuss]
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
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5
Sample Output
0
0
0
1
HINT
对于100%的数据，1<=n,c,m<=10^5
Source
感觉是一道很好的题。
感谢PoPoQQQ的题解和hzw的代码，研究一节音乐课一后终于懂了
。。然而因为昨天太忙了。。。现在才有时间打出来
。。
我们先预处理任意两个块之间的答案，直接暴力扫一遍就可以得到
然后考虑询问，因为我们已经知道了中间块的答案，所以只要考虑两头的块的数字对答案的影响。所以我们暴力考虑每一个在两头中多出来的数字，求在询问区间中出现的总次数和在中间完整块出现的次数，然后判断这个数对答案是否有影响。至于如何求一个数在区间中出现的次数。。可以二分上边界和下边界。。然后减一下。。
每块大小：\(\sqrt {n\over log(n)}\) 复杂度：\(n\sqrt{n}*log(n)\)
附带从hzw里偷来的块大小的分析：
设分块大小为：\(x\)，分块数为：\(\frac nx\)，预处理：\(\frac nx *n\)
\(n\)与\(m\)同级，视为\(n\)个询问，每次询问二分\(x\)次\(n*x*log(n)\)（除非相同的数字很多，否则\(log(n)\)会很小）。
\(n*(x*log(n)+\frac nx)\)
则分块大小为：\(\sqrt {n\over log(n)}\)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6;
const int M = 2e3;
struct data{int v,id;} b[N];
int n,m,Q,blk,lastans,pos[N],L[M],R[M],a[N],tmp[N],vis[N],f[M][M],fis[N],last[N],c;
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
bool cmp(data a,data b){if (a.v==b.v) return a.id<b.id;return a.v<b.v;}
void Prepare(){
for (int i=1;i<=m;i++){
int tot = 0;
for (int j=L[i];j<=n;j++) tmp[a[j]] = 0;
for (int j=L[i];j<=n;j++){
if (!(tmp[a[j]]&1) && tmp[a[j]]) tot--;
tmp[a[j]]++;
if (!(tmp[a[j]]&1)) tot++;
f[i][pos[j]] = tot;
}
}
for (int i=1;i<=n;i++) b[i].v = a[i],b[i].id = i;
sort(b+1,b+1+n,cmp);
for (int i=1;i<=n;i++){
if (!fis[b[i].v]) fis[b[i].v] = i;
last[b[i].v] = i;
}
}
int findup(int x,int val){
int l = fis[val],r = last[val],ans = 0;
while (l<=r){
int mid = (l+r)>>1;
if (b[mid].id<=x) ans = mid-fis[val],l = mid+1;
else r = mid-1;
}
return ans;
}
int finddown(int x,int val){
int l = fis[val],r = last[val],ans = last[val]+1;
while (l<=r){
int mid = (l+r)>>1;
if (b[mid].id>=x) ans = mid-fis[val],r = mid-1;
else l = mid+1;
}
return ans;
}
int find(int l,int r,int val){return max(findup(r,val)-finddown(l,val)+1,0);}
int Query(int x,int y){
int ans = 0;
if (pos[x]==pos[y] || pos[x]+1==pos[y]){
for (int i=x;i<=y;i++){
int A = a[i];if (vis[A]) continue;
int t = find(x,y,A);
if (!(t&1)) ans++;
vis[A] = 1;
}
for (int i=x;i<=y;i++) vis[a[i]] = 0;
return ans;
}
else {
int l = L[pos[x]+1],r = R[pos[y]-1];
ans = f[pos[x]+1][pos[y]-1];
for (int i=x;i<l;i++){
int A = a[i];if (vis[A]) continue;
int t2 = find(l,r,A),t1 = find(x,y,A);
if (!(t1&1)) {if (t2&1 || !t2) ans++;}
else if (!(t2&1) && t2) ans--;
vis[A] = 1;
}
for (int i=r+1;i<=y;i++){
int A = a[i];if (vis[A]) continue;
int t2 = find(l,r,A),t1 = find(x,y,A);
if (!(t1&1)) {if (t2&1 || !t2) ans++;}
else if (!(t2&1) && t2) ans--;
vis[A] = 1;
}
for (int i=x;i<l;i++) vis[a[i]] = 0;
for (int i=r+1;i<=y;i++) vis[a[i]] = 0;
return ans;
}
}
int main(){
freopen("2821.in","r",stdin);
freopen("2821.out","w",stdout);
n = read();c = read();Q = read();
for (int i=1;i<=n;i++) a[i] = read();
blk = sqrt((double)n/log((double)n)*log(2));
if (n%blk) m = n/blk+1;
else m = n/blk;
for (int i=1;i<=n;i++) pos[i] = (i-1)/blk+1;
for (int i=1;i<=m;i++) L[i] = (i-1)*blk+1,R[i] = min(i*blk,n);
Prepare();
for (int i=1;i<=Q;i++){
int l = read(),r = read();
int x = (l+lastans)%n+1,y = (r+lastans)%n+1;
if (x>y) swap(x,y);
lastans = Query(x,y);
printf("%d\n",lastans);
}
}
评论 (0)
