题面传送门 可以算一道线段树维护hash的模板题了吧。 hash要满足两个条件:相同的数hash值一定一样与hash冲突尽量少。 这道题hash序列可以用幂次方来hash 然后用线段树随便维护一下就好了。 代码实现:
#include<cstdio> #include<algorithm> #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,smax[2000039],smin[2000039],l,r,mid,tots[500039]; unsigned long long sum[2000039],a[500039],ans1,ans2,ans3,now[500039]; inline void jianshu(int l,int r,int now){ if(l==r) {smax[now]=smin[now]=a[l];sum[now]=a[l]*a[l];return;} int m=(l+r)>>1; jianshu(l,m,now<<1); jianshu(m+1,r,now<<1|1); smax[now]=max(smax[now<<1],smax[now<<1|1]); smin[now]=min(smin[now<<1],smin[now<<1|1]); sum[now]=sum[now<<1]+sum[now<<1|1]; } inline void get(int x,int y,int l,int r,int now){ if(l==r){smax[now]=smin[now]=y;sum[now]=(long long)y*y;return;} int m=(l+r)>>1; if(x<=m) get(x,y,l,m,now<<1); else get(x,y,m+1,r,now<<1|1); smax[now]=max(smax[now<<1],smax[now<<1|1]); smin[now]=min(smin[now<<1],smin[now<<1|1]); sum[now]=sum[now<<1]+sum[now<<1|1]; } inline void find(int x,int y,int l,int r,int now){ if(x<=l&&r<=y) {ans1=max(ans1,smax[now]),ans2=min(ans2,smin[now]),ans3+=sum[now];return;} int m=(l+r)>>1; if(x<=m) find(x,y,l,m,now<<1); if(y>m) find(x,y,m+1,r,now<<1|1); return; } int main(){ // freopen("1.in","r",stdin); register int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%lld",&a[i]),now[i]=a[i]; sort(now+1,now+n+1); now[0]=now[1]-1; for(i=1;i<=n;i++){ tots[i]=tots[i-1]; if(now[i]!=now[i-1]) tots[i]++; } for(i=1;i<=n;i++){ l=0;r=n+1; while(l+1<r){ mid=(l+r)>>1; if(now[mid]<a[i]) l=mid; else r=mid; } a[i]=tots[r]; } jianshu(1,n,1); for(i=1;i<=n;i++){ scanf("%d%d%d",&x,&y,&z); if(x==1)get(y,z,1,n,1); else { ans1=ans3=0;ans2=1e9; find(y,z,1,n,1); if(ans1-ans2==z-y&&ans1*(ans1+1)*(2*ans1+1)/6-ans2*(ans2-1)*(2*ans2-1)/6==ans3) printf("damushen\n"); else printf("yuanxing\n"); } } }