正題

題目鏈接:https://darkbzoj.tk/problem/4722

---

題目大意

給出一個長度為$n$的序列值域為$[0,v)$，要求支持操作

詢問一個區間能否找到兩個沒有交的非空下標集合使得這些位置的和加上集合的大小相等。

區間立方然后取模$v$。

$1\le n\le 10^5,1\le v\le 1000$

---

解題思路

考慮如果我們選出了兩個有交的集合相等，那么我們把交的部分去掉就變成無交的了，所以無需考慮有沒有交。

然后根據抽屜原理對于$n$個元素所有集合總共能表示出$2^n$個和，但是和最大只有$n\times v$所以如果$2^n>n\times v$時就肯定有解，那么此時會發現當$v$最大時$n$超過$13$就肯定有解。

如果元素個數小于或等于$13$時我們可以先預處理出一個倍增數組加上一個樹狀數組來統計每個數最終被修改了多少次就可以得到每個數的具體值了。然后考慮$dp$，因為值域比較大可以用$bitset$優化就好了。

時間復雜度$O(v\log m+m\log n+m\frac{13v}{\omega })$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<bitset> #define lowbit(x) (x&-x) using namespace std; const int N=1e5+10; int n,m,v,f[1100][18],t[N],a[N]; bitset<13001>b; void Change(int x,int val){while(x<=n){t[x]+=val;x+=lowbit(x);}return; } int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } int Step(int x,int b){for(int i=0;(1<<i)<=b;i++)if((b>>i)&1)x=f[x][i];return x; } int main() {scanf("%d%d%d",&n,&m,&v);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=0;i<v;i++)f[i][0]=i*i*i%v;for(int j=1;(1<<j)<=n;j++)for(int i=0;i<v;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(op==2)Change(l,1),Change(r+1,-1);else{if(r-l+1>13){puts("Yuno");continue;}b.reset();b[0]=1;bool flag=0;for(int i=l;i<=r;i++){int w=Step(a[i],Ask(i))+1;if((b&(b<<w)).any()){flag=1;break;}b=b|(b<<w);}if(flag)puts("Yuno");else puts("Yuki");}}return 0; }

總結

以上是生活随笔為你收集整理的bzoj#4722-由乃【倍增,抽屉原理,bitset】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。