[CodeForces 52C]Circular RMQ

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目传送门

评分：省选/NOI-，难度：普及+/提高

这题真的和RMQ没有半点关系，只需要一个裸的线段树，连pushdown都不需要，只需要两种操作：区间修改和区间求最小值，在回溯时加上标记即可，唯一有点思维含量的是对环的处理，如果左端点大于了右端点，就维护(l,n)(1,r)，否则正常维护即可，不知道线段树怎么打的可以看我的博客：线段树

下面给出参考代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 struct node

 {

     long long l,r,w,tag;

 }tree[];

 long long n,m,q,x,y,k,ans;

 void build(long long l,long long r,long long k)

 {

     tree[k].l=l;tree[k].r=r;

     if(l==r)

     {

         scanf("%lld",&tree[k].w);

         return;

     }

     long long mid=(l+r)/;

     build(l,mid,k*);

     build(mid+,r,k*+);

     tree[k].w=min(tree[k*].w,tree[k*+].w);

 }

 void add(long long k,long long w,long long ll,long long rr)

 {

     long long l=tree[k].l,r=tree[k].r;

     if(l>=ll&&r<=rr)

     {

         tree[k].tag+=w;

         return;

     }

     //cout<<k<<" "<<l<<" "<<r<<endl;

     long long mid=(l+r)/;

     //cout<<x<<" "<<y<<endl;

     if(ll<=mid)add(k*,w,ll,rr);

     if(rr>mid)add(k*+,w,ll,rr);

     tree[k].w=min(tree[k*].w+tree[k*].tag,tree[k*+].w+tree[k*+].tag);

     return;

 }

 long long query(long long k,long long ll,long long rr)

 {

     if(tree[k].l>=ll&&tree[k].r<=rr)

     {

         return tree[k].w+tree[k].tag;

     }

     if(tree[k].l>rr||tree[k].r<ll)

     {

         return ;

     }

     long long mid=(tree[k].l+tree[k].r)/,lc,rc;

     lc=query(k*,ll,rr);

     rc=query(k*+,ll,rr);

     return min(lc,rc)+tree[k].tag;

 }

 int main()

 {

     cin>>n;

     build(,n,);

     cin>>m;

     for(long long i=;i<=m;i++)

     {

         cin>>x>>y;

         x++;y++;

         char c=getchar();

         if(c=='\n')

         {

             //4 1

             ans=;

             if(x>y)cout<<min(query(,x,n),query(,,y));

             else cout<<query(,x,y);

             cout<<endl;

         }

         else

         {

             cin>>q;

             if(x>y)add(,q,x,n),add(,q,,y);

             else add(,q,x,y);

         }

     }

     return ;

 }