中山大兴网站建设,wordpress博客备案,建设99工程教育网论坛官网,杭州网站快速备案正题
题目链接:https://darkbzoj.tk/problem/4722 题目大意
给出一个长度为nnn的序列值域为[0,v)[0,v)[0,v)#xff0c;要求支持操作
询问一个区间能否找到两个没有交的非空下标集合使得这些位置的和加上集合的大小相等。区间立方然后取模vvv。 1≤n≤105,1≤v≤10001\leq …正题
题目链接:https://darkbzoj.tk/problem/4722 题目大意
给出一个长度为nnn的序列值域为[0,v)[0,v)[0,v)要求支持操作
询问一个区间能否找到两个没有交的非空下标集合使得这些位置的和加上集合的大小相等。区间立方然后取模vvv。
1≤n≤105,1≤v≤10001\leq n\leq 10^5,1\leq v\leq 10001≤n≤105,1≤v≤1000 解题思路
考虑如果我们选出了两个有交的集合相等那么我们把交的部分去掉就变成无交的了所以无需考虑有没有交。
然后根据抽屉原理对于nnn个元素所有集合总共能表示出2n2^n2n个和但是和最大只有n×vn\times vn×v所以如果2nn×v2^nn\times v2nn×v时就肯定有解那么此时会发现当vvv最大时nnn超过131313就肯定有解。
如果元素个数小于或等于131313时我们可以先预处理出一个倍增数组加上一个树状数组来统计每个数最终被修改了多少次就可以得到每个数的具体值了。然后考虑dpdpdp因为值域比较大可以用bitsetbitsetbitset优化就好了。
时间复杂度O(vlogmmlognm13vω)O(v\log mm\log nm\frac{13v}{\omega})O(vlogmmlognmω13v) code
#includecstdio
#includecstring
#includealgorithm
#includebitset
#define lowbit(x) (x-x)
using namespace std;
const int N1e510;
int n,m,v,f[1100][18],t[N],a[N];
bitset13001b;
void Change(int x,int val){while(xn){t[x]val;xlowbit(x);}return;
}
int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;
}
int Step(int x,int b){for(int i0;(1i)b;i)if((bi)1)xf[x][i];return x;
}
int main()
{scanf(%d%d%d,n,m,v);for(int i1;in;i)scanf(%d,a[i]);for(int i0;iv;i)f[i][0]i*i*i%v;for(int j1;(1j)n;j)for(int i0;iv;i)f[i][j]f[f[i][j-1]][j-1];while(m--){int op,l,r;scanf(%d%d%d,op,l,r);if(op2)Change(l,1),Change(r1,-1);else{if(r-l113){puts(Yuno);continue;}b.reset();b[0]1;bool flag0;for(int il;ir;i){int wStep(a[i],Ask(i))1;if((b(bw)).any()){flag1;break;}bb|(bw);}if(flag)puts(Yuno);else puts(Yuki);}}return 0;
}
