Adnan and the Burned drivers

Adnan and the Burned drivers

题目链接：Adnan and the Burned drivers

显然维护正反字符串的哈希值，那么直接判断即可。

由于有修改，所以用线段树维护。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=1e9+3,base=131;
int n,m,s1[N<<2],s2[N<<2],pw[N]={1},q1,q2; char str[N],ch[5];
#define mid (l+r>>1)
void change(int p,int l,int r,int x,int v){if(l==r){s1[p]=s2[p]=v; return ;}if(x<=mid)	change(p<<1,l,mid,x,v);else	change(p<<1|1,mid+1,r,x,v);s1[p]=(s1[p<<1]*pw[r-mid]+s1[p<<1|1])%mod;s2[p]=(s2[p<<1]+s2[p<<1|1]*pw[mid-l+1])%mod;
}
int ask(int p,int l,int r,int ql,int qr,int k){if(l==ql&&r==qr)	return k?s1[p]:s2[p];if(qr<=mid)	return ask(p<<1,l,mid,ql,qr,k);else if(ql>mid)	return ask(p<<1|1,mid+1,r,ql,qr,k);else if(k)	return (ask(p<<1,l,mid,ql,mid,k)*pw[qr-mid]+ask(p<<1|1,mid+1,r,mid+1,qr,k))%mod;else	return (ask(p<<1,l,mid,ql,mid,k)+ask(p<<1|1,mid+1,r,mid+1,qr,k)*pw[mid-ql+1])%mod;
}
inline void solve(){cin>>n>>m; scanf("%s",str+1);for(int i=1;i<=n;i++)	change(1,1,n,i,str[i]);for(int i=1,op,l,r;i<=m;i++){scanf("%lld %lld",&op,&l);if(op==1)	scanf("%s",ch),change(1,1,n,l,str[l]=ch[0]);else{scanf("%lld",&r);if(r==l){puts("Adnan Wins");	continue;}		else if((r-l+1)&1LL) q1=ask(1,1,n,l,mid-1,1),q2=ask(1,1,n,mid+1,r,0);else q1=ask(1,1,n,l,mid,1),q2=ask(1,1,n,mid+1,r,0);puts(q1==q2?"Adnan Wins":"ARCNCD!");}}
}
signed main(){for(int i=1;i<=1e5;i++)	pw[i]=pw[i-1]*base%mod;int T; cin>>T; while(T--) solve();return 0;
}