分析:
这道题,出看完是线段树的模板题。
但由于1<=m<=107,我们的时间复杂度最高会达到O(mlogn+nlogn),初看是铁定过不了的。
但由于不知道其他方法只好交了个线段树,结果呢,AC了!!!
那么我们在重新感性的理解一下!
随着vi的变大,我们线段树修改的可能性会越来越低!
这使我们的修改操作O(mlogn)跑不满,甚至远远达不到这种高度。
于是你会发现,线段树莫名很香!!!
值得注意的是,其中x,y,z的数据使unsigned long long类型的,我们用scanf输入时一定一定要用scanf("%llu%lly%llu",&x,&y,&z),不然,100分秒变20分!
#include<bits/stdc++.h> using namespace std; #define re register int #define LL unsigned long long const int N=1e5+5; const LL mo=1<<30; struct segment{int a, b; LL v, lzy;}tr[N<<3]; void build(const int p,const int x,const int y) { tr[p]=(segment){x,y,0ll,0ll}; if(x!=y) { int mid=(x+y)>>1; build(p<<1,x,mid); build(p<<1|1,mid+1,y); } return; } inline void putdown(const int p) { if(tr[p].a==tr[p].b||tr[p].lzy==0ll)return; LL tmp=tr[p].lzy; tr[p].lzy=0ll; int ls=p<<1,rs=p<<1|1; if(tr[ls].v<tmp) { tr[ls].v=tmp; tr[ls].lzy=tmp; } if(tr[rs].v<tmp) { tr[rs].v=tmp; tr[rs].lzy=tmp; } return; } void modi(const int p,const int x,const int y,const LL d) { if(tr[p].v>=d)return; if(x<=tr[p].a&&tr[p].b<=y) { tr[p].v=d; tr[p].lzy=d; return; } if(tr[p].lzy)putdown(p); int mid=(tr[p].a+tr[p].b)>>1, ls=p<<1, rs=p<<1|1; if(x<=mid)modi(ls,x,y,d); if(y>mid)modi(rs,x,y,d); tr[p].v=min(tr[ls].v,tr[rs].v); return; } void query(const int p) { if(tr[p].a==tr[p].b) { printf("%llu ",tr[p].v); return; } if(tr[p].lzy)putdown(p); query(p<<1); query(p<<1|1); return; } LL A, B, C; inline LL RNG() { A ^= A << 16; A ^= A >> 5; A ^= A << 1; LL w = A ^ B ^ C; A = B; B = C; C = w; return C; } signed main() { int n, m; scanf("%d%d%llu%lld%llu",&n,&m,&A,&B,&C); build(1, 1, n); while(m--) { LL x,y,z,r1=RNG(),r2=RNG(),r3=RNG(); x=min(r1%n,r2%n)+1; y=max(r1%n,r2%n)+1; z=r3%mo; modi(1, x, y, z); }query(1); return 0; }
“一朝读入惨报错,泪后才知cin好”----《kzsn语录》kzsn