首页 > 代码库 > Codeforces 803G Periodic RMQ Problem ST表+动态开节点线段树

Codeforces 803G Periodic RMQ Problem ST表+动态开节点线段树

思路:

(我也不知道这是不是正解)

ST表预处理出来原数列的两点之间的min

再搞一个动态开节点线段树

节点记录ans 和标记

lazy=-1 当前节点的ans可用  lazy=0 没被覆盖过 else 区间覆盖

 

push_up的时候要注意好多细节,,

数组尽量往大开 

//By SiriusRen#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=100050;int n,k,q,op,xx,b[N],f[N][20],lson[N<<7],rson[N<<7],root,cnt;int lazy[N<<7],ans[N<<7],base[N];//lazy=-1 废了  lazy=0 原数列 else 区间覆盖int RMQ(int x,int y){    int t=base[y-x+1];     return min(f[x][t],f[y-(1<<t)+1][t]);}int qry(int l,int r){    if(r-l>=n)return RMQ(1,n);    else{        l=(l-1)%n+1,r=(r-1)%n+1;        if(l>r)return min(RMQ(1,r),RMQ(l,n));        else return RMQ(l,r);    }}void push_down(int pos){    if(!lson[pos])lson[pos]=++cnt;lazy[lson[pos]]=lazy[pos];    if(!rson[pos])rson[pos]=++cnt;lazy[rson[pos]]=lazy[pos];}void insert(int l,int r,int &pos,int L,int R,int wei){    if(!pos)pos=++cnt;//    printf("l=%lld r=%lld pos=%d\n",l,r,pos);    if(lazy[pos]&&~lazy[pos]){        ans[pos]=lazy[pos];        push_down(pos);        lazy[pos]=-1;    }    if(l>=L&&r<=R){ans[pos]=lazy[pos]=xx;return;}    int mid=(l+r)>>1;    if(mid<L)insert(mid+1,r,rson[pos],L,R,wei);    else if(mid>=R)insert(l,mid,lson[pos],L,R,wei);    else insert(l,mid,lson[pos],L,R,wei),insert(mid+1,r,rson[pos],L,R,wei);    int temp=0x3f3f3f3f;    if(lson[pos]){        if(!lazy[lson[pos]])temp=qry(l,mid);        else if(lazy[lson[pos]]==-1)temp=ans[lson[pos]];        else temp=lazy[lson[pos]];    }    else temp=qry(l,mid);    if(lazy[rson[pos]]){        if(!lazy[rson[pos]])temp=min(temp,qry(mid+1,r));        else if(lazy[rson[pos]]==-1)temp=min(temp,ans[rson[pos]]);        else temp=min(temp,lazy[rson[pos]]);    }    else temp=min(temp,qry(mid+1,r));    ans[pos]=temp,lazy[pos]=-1;}int query(int l,int r,int pos,int L,int R){    if(l==L&&r==R){        if(lazy[pos]==-1)return ans[pos];        else if(!lazy[pos])return qry(l,r);        else return lazy[pos];    }    if(!pos)return qry(L,R);    if(lazy[pos]&&~lazy[pos])return lazy[pos];    int mid=(l+r)>>1;    if(mid<L)return query(mid+1,r,rson[pos],L,R);    else if(mid>=R)return query(l,mid,lson[pos],L,R);    else return min(query(l,mid,lson[pos],L,mid),query(mid+1,r,rson[pos],mid+1,R));}void DFS(int l,int r,int pos){    printf("l=%d r=%d pos=%d lazy[pos]=%d ans[pos]=%d\n",l,r,pos,lazy[pos],ans[pos]);    int mid=(l+r)>>1;    if(lson[pos])DFS(l,mid,lson[pos]);    if(rson[pos])DFS(mid+1,r,rson[pos]);}int main(){    scanf("%d%d",&n,&k);    base[0]=-1;    for(int i=1;i<=n;i++)scanf("%d",&b[i]),f[i][0]=b[i],base[i]=base[i>>1]+1;    for(int j=1;j<=19;j++)        for(int i=1;i+(1<<(j-1))<=n;i++)            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);    scanf("%d",&q);    while(q--){        int l,r;        scanf("%d%d%d",&op,&l,&r);        if(op==1){            scanf("%d",&xx);            insert(1,n*k,root,l,r,xx);        }        else{            printf("%d\n",query(1,n*k,root,l,r));        }//        DFS(1,1ll*n*k,1);    }}/*8 45 6 1 3 3 2 9 6 141 10 19 22 14 26*/ 

 

Codeforces 803G Periodic RMQ Problem ST表+动态开节点线段树