Reverse and Swap CodeForces - 1401 F 线段树 + 思维-白红宇的个人博客

Reverse and Swap CodeForces - 1401 F 线段树 + 思维

发布日期：2021-09-25 23:57:58 浏览次数：17 分类：技术文章

本文共 1626 字，大约阅读时间需要 5 分钟。

题目：要求实现四个操作如下

第一个第四个用线段树比较容易了。

第二个和第三个都是在分成 2 ^ k 长度区间操作，比较容易想到线段树就是分成 n+1 层，每层都由 2 ^ k 长度区间构成。规定根节点为第 n 层，叶子节点为第 0 层。

先看第三个swap：相当于交换线段树两个相邻区间，也就是相当于访问的时候直接访问另一个区间即可。可以用一个变量来记录以下是否需要改变访问的左右结点。比如当前swap的是第 k 层，那么只需要改变第 k + 1 层标记即可。

第二个跟第三个道理相同，假如当前需要reverse第 k 层，意味着从 0 ~ k 层都反转了，那么需要把 0 ~ k 层的标记都 + 1 。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int a[N],rev[N];struct Node{ int l,r; LL sum;}tr[N<<2];void pushup(int u){ tr[u].sum=tr[L].sum+tr[R].sum;}void build(int u,int l,int r){ tr[u]={ l,r,0}; if(l==r) { tr[u].sum=a[l]; return; } build(L,l,Mid),build(R,Mid+1,r); pushup(u);}void modify(int l,int r,int rt,int p,int x,int depth){ if(l==r) { tr[rt].sum=x; return; } int mid=l+r>>1; if(p<=mid) modify(l,mid,rt*2+(rev[depth]==1),p,x,depth-1); else modify(mid+1,r,rt*2+1-(rev[depth]==1),p,x,depth-1); tr[rt].sum=tr[rt*2].sum+tr[rt*2+1].sum;}LL query(int rl,int rr,int rt,int l,int r,int depth){ if(rl>=l&&rr<=r) return tr[rt].sum; int mid=rl+rr>>1; LL ans=0; if(l<=mid) ans+=query(rl,mid,rt*2+(rev[depth]==1),l,r,depth-1); if(r>mid) ans+=query(mid+1,rr,rt*2+1-(rev[depth]==1),l,r,depth-1); return ans;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d%d",&n,&m); for(int i=1;i<=1ll<

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/108240522 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Splay 板子

下一篇：HDU - 1688 Sightseeing 最短路和次短路计数

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章