題目大意：給出一個長度為 n 的序列，接下來有 m 次操作，每次操作分為下列兩種類型：

1 l r：區間 [ l , r ] 內的所有數都加 1 并對?65536 取模，也就是 i ∈ [ l , r ] ，有 a[ i ] =( a[ i ] + 1?) % 65536

2 x y len：查詢兩段區間 [ x , x + len - 1 ] 和 [ y , y + len - 1 ] 內的序列是否相同

題目分析：第一種操作可以轉化成區間更新，第二種操作可以轉換成區間查詢和哈希，所以不難想到使用線段樹去維護每個位置的加權哈希值，這樣就可以輕松更新和訪問了

如果將操作一中的對?65536 取模刪除掉，這就是一個非常簡單的問題了，首先設置權值：f[ 1 ] = base，f[ 2 ] = base^2 ... f[ i ] = base^i，每個葉子節點的權值就是 val[ i ] * f[ i ] ，每次區間更新也就是 [ l , r ] 這段區間加上 f[ l ] + f[ l + 1 ] + ... + f[ r ] ，如此遞歸下去即可

那么操作一加上了對?65536 取模會有什么影響呢？有一些數字從?65535 加一變成 65536 之后，包含這些數字的區間 [ l , r ] 就不再是單純的加上?f[ l ] + f[ l + 1 ] + ... + f[ r ] 了，還需要特殊處理從?65535 變成?65536 的這些位置，因為 65536 取模后就換成 0 了

然后是一個比較簡單的思維點了，我們稱一個數字從 65535 加到 65536?為溢出，因為整個序列的長度為 n ，總共的操作次數為 m，所以最多會出現 n * m / 65536 次溢出，估算一下是 5e6 級別的，對于這些溢出，我們完全可以單獨處理

到此為止直接寫線段樹就可以了，線段樹中多維護一個最大值用來暴力維護溢出的情況，總的時間復雜度為：O( n*q*logn/65536 + qlogn )

然后出題人昨天也表明了，這個題卡了自然溢出，所以需要自己設置一個基數和模數用來哈希

代碼：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e5+100;const int base=2333333;const int mod=999999998;LL f[N];struct Node {int l,r,len;LL base,Hash,mmax,lazy; }tree[N<<2];void pushup(int k) {tree[k].Hash=(tree[k<<1].Hash+tree[k<<1|1].Hash)%mod;tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); }void pushdown(int k) {if(tree[k].lazy){LL lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].Hash=(tree[k<<1].Hash+tree[k<<1].base*lz)%mod;tree[k<<1|1].Hash=(tree[k<<1|1].Hash+tree[k<<1|1].base*lz)%mod;tree[k<<1].mmax+=lz;tree[k<<1|1].mmax+=lz;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].len=r-l+1;tree[k].lazy=0;if(l==r){scanf("%lld",&tree[k].mmax);tree[k].base=f[l];tree[k].Hash=tree[k].base*tree[k].mmax%mod;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].base=(tree[k<<1].base+tree[k<<1|1].base)%mod;pushup(k); }void update(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].Hash=(tree[k].Hash+tree[k].base)%mod;tree[k].mmax++;tree[k].lazy++;return;}pushdown(k);update(k<<1,l,r);update(k<<1|1,l,r);pushup(k); }void update_mod(int k)//記錄下來所有最大值為65536的位置單獨更新 {if(tree[k].mmax<65536)return;if(tree[k].l==tree[k].r){tree[k].mmax=0;tree[k].Hash=0;return;}pushdown(k);update_mod(k<<1);update_mod(k<<1|1);pushup(k); }LL query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].Hash;pushdown(k);return (query(k<<1,l,r)+query(k<<1|1,l,r))%mod; }bool check(int x,int y,int len) {if(x>y)swap(x,y);LL ans1=query(1,x,x+len-1)*f[y-x]%mod;LL ans2=query(1,y,y+len-1);return ans1==ans2; }void init() {f[0]=1;for(int i=1;i<N;i++)f[i]=f[i-1]*base%mod; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n,m;scanf("%d%d",&n,&m);build(1,1,n);while(m--){int op;scanf("%d",&op);if(op==1){int l,r;scanf("%d%d",&l,&r);update(1,l,r);update_mod(1);}else{int x,y,len;scanf("%d%d%d",&x,&y,&len);printf("%s\n",check(x,y,len)?"yes":"no");}}return 0; }

?

總結

以上是生活随笔為你收集整理的2020CCPC(威海) - Caesar Cipher(线段树+哈希)的全部內容，希望文章能夠幫你解決所遇到的問題。

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