原题链接：http://codeforces.com/contest/803/problem/G
题解：
半夜三点闲来无事，激情刷题2333333
看到网上有dalao直接一颗线段树就搞定了。。。感觉自己白写了这么多啊？
其实考虑到整个序列是一个循环的，很容易想到会有很多的重复的状态，那么我们可以通过主席树来将所有的冗余状态合并起来进行维护。
更新操作可以拆分为，更新一整个周期的操作+更新周期的一部分的操作。对于更新一整个周期的操作，我们可以利用线段树区间更新最小值。对于局部的操作，可以直接在主席树上更新，然后将新的最小值插入到线段树上，注意，这类更新之前，我们要判断这个周期是否之前被操作过，相当于一个懒惰标记下放的过程。
查询的时候，也分为两种，覆盖一整个周期的+覆盖部分周期的，和更新类似，只要分类处理，下放懒惰标记就好了。。。
题目貌似不难，就是我写的太复杂了？还是菜啊。。。。
#include<bits/stdc++.h> #define xx first #define yy second #define mp make_pair using namespace std; const int MAXN=1e5+5; const int M=MAXN*100; const int SZ=1e4+5; int n,q,tot,k,tot2; int b[MAXN]; int T[MAXN/10],lson[M],rson[M],c[M],lazy[M],book[M],sv[M]; inline int getnode() { int ret; if(tot2) { ret=sv[tot2--]; } else { ret=tot++; } book[ret]++; lazy[ret]=rson[ret]=lson[ret]=c[ret]=0; return ret; } inline void del(int now) { if(now==0) return ; book[now]--; if(!book[now]) { sv[++tot2]=now; } } inline void push_up(int now) { if(!lson[now]&&!rson[now]) return ; c[now]=min(c[lson[now]],c[rson[now]]); } inline void push_down(int now) { int newroot,root; if(lazy[now]) { if(lson[now]) { newroot=getnode(); root=lson[now]; lson[newroot]=lson[root]; rson[newroot]=rson[root]; del(root); lson[now]=newroot; c[newroot]=lazy[now]; lazy[newroot]=lazy[now]; } if(rson[now]) { newroot=getnode(); root=rson[now]; lson[newroot]=lson[root]; rson[newroot]=rson[root]; del(root); rson[now]=newroot; c[newroot]=lazy[now]; lazy[newroot]=lazy[now]; } lazy[now]=0; } } int build(int l,int r) { int root=getnode(); book[root]=k; if(l==r) { c[root]=b[l]; return root; } int mid=(l+r)>>1; lson[root]=build(l,mid); rson[root]=build(mid+1,r); push_up(root); return root; } inline int update(int L,int R,int l,int r,int root,int val) { int newroot=getnode(); push_down(root); lson[newroot]=lson[root]; rson[newroot]=rson[root]; if(L<=l&&r<=R) { c[newroot]=val; lazy[newroot]=val; del(root); return newroot; } int mid=(l+r)>>1; if(L<=mid) { lson[newroot]=update(L,R,l,mid,lson[root],val); } if(R>mid) { rson[newroot]=update(L,R,mid+1,r,rson[root],val); } del(root); push_up(newroot); return newroot; } inline int query(int L,int R,int l,int r,int root) { if(L<=l&&r<=R) { return c[root]; } int mid=(l+r)>>1; push_down(root); int ret=1e9; if(L<=mid) { ret=min(ret,query(L,R,l,mid,lson[root])); } if(R>mid) { ret=min(ret,query(L,R,mid+1,r,rson[root])); } return ret; } struct segmentTree { pair<int,int> tree[SZ<<2],lazy[SZ<<2]; void push_up(int rt) { tree[rt]=min(tree[rt<<1],tree[rt<<1|1]); } void push_down(int rt) { if(lazy[rt].xx) { tree[rt<<1]=lazy[rt]; tree[rt<<1|1]=lazy[rt]; lazy[rt<<1]=lazy[rt]; lazy[rt<<1|1]=lazy[rt]; lazy[rt]=mp(0,0); } } void update(int L,int R,pair<int,int> val,int l,int r,int rt) { if(L>R) return ; if(L<=l&&r<=R) { tree[rt]=val; lazy[rt]=val; return ; } int mid=(l+r)>>1; push_down(rt); if(L<=mid) { update(L,R,val,l,mid,rt<<1); } if(R>mid) { update(L,R,val,mid+1,r,rt<<1|1); } push_up(rt); } pair<int,int> query(int pos,int l,int r,int rt) { if(l==r) { return tree[rt]; } int mid=(l+r)>>1; push_down(rt); if(pos<=mid) return query(pos,l,mid,rt<<1); if(pos>mid) return query(pos,mid+1,r,rt<<1|1); } int querymin(int L,int R,int l,int r,int rt) { if(L>R) return 1e9; if(L<=l&&r<=R) { return tree[rt].xx; } int mid=(l+r)>>1; int ret=1e9; push_down(rt); if(L<=mid) ret=min(ret,querymin(L,R,l,mid,rt<<1)); if(R>mid) ret=min(ret,querymin(L,R,mid+1,r,rt<<1|1)); return ret; } }se; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); tot=1;c[0]=1e9;tot2=0; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) { scanf("%d",&b[i]); } T[0]=build(0,n-1); se.update(0,0,mp(c[T[0]],0),0,k-1,1); for(int i=1;i<k;i++) { T[i]=T[0]; se.update(i,i,mp(c[T[i]],0),0,k-1,1); } scanf("%d",&q); while(q--) { int op; scanf("%d",&op); if(op==1) { int l,r,x,L,R; scanf("%d%d%d",&l,&r,&x); l--,r--; L=l/n;R=r/n; se.update(L+1,R-1,mp(x,1),0,k-1,1); int ll,rr; ll=l%n;rr=r%n; pair<int,int> pii; if(L==R) { pii=se.query(L,0,k-1,1); if(pii.yy) { T[L]=update(0,n-1,0,n-1,T[L],pii.xx); } T[L]=update(ll,rr,0,n-1,T[L],x); se.update(L,L,mp(c[T[L]],0),0,k-1,1); } else { pii=se.query(L,0,k-1,1); if(pii.yy) { T[L]=update(0,n-1,0,n-1,T[L],pii.xx); } T[L]=update(ll,n-1,0,n-1,T[L],x); se.update(L,L,mp(c[T[L]],0),0,k-1,1); pii=se.query(R,0,k-1,1); if(pii.yy) { T[R]=update(0,n-1,0,n-1,T[R],pii.xx); } T[R]=update(0,rr,0,n-1,T[R],x); se.update(R,R,mp(c[T[R]],0),0,k-1,1); } } if(op==2) { int l,r,L,R,ans=1e9; scanf("%d%d",&l,&r); l--,r--; L=l/n;R=r/n; ans=min(ans,se.querymin(L+1,R-1,0,k-1,1)); int ll,rr; ll=l%n;rr=r%n; pair<int,int> pii; if(L==R) { pii=se.query(L,0,k-1,1); if(pii.yy) { T[L]=update(0,n-1,0,n-1,T[L],pii.xx); } ans=min(ans,query(ll,rr,0,n-1,T[L])); if(pii.yy) { se.update(L,L,mp(c[T[L]],0),0,k-1,1); } } else { pii=se.query(L,0,k-1,1); if(pii.yy) { T[L]=update(0,n-1,0,n-1,T[L],pii.xx); } ans=min(ans,query(ll,n-1,0,n-1,T[L])); if(pii.yy) { se.update(L,L,mp(c[T[L]],0),0,k-1,1); } pii=se.query(R,0,k-1,1); if(pii.yy) { T[R]=update(0,n-1,0,n-1,T[R],pii.xx); } ans=min(ans,query(0,rr,0,n-1,T[R])); if(pii.yy) { se.update(R,R,mp(c[T[R]],0),0,k-1,1); } } printf("%d\n",ans); } } return 0; }
