Educational Codeforces Round 36 (Rated for Div. 2) E 线段树 || 珂朵莉树-白红宇的个人博客

Educational Codeforces Round 36 (Rated for Div. 2) E 线段树 || 珂朵莉树

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

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

尘封多个月的题。。。以前看见要动态开点没学，拿线段树敲崩了，秃然想起来就补上了。

题意就是比较简单，给定一个全1序列，给你若干区间，两个操作，每次操作后区间 1 ~ n 1的个数。：

(1)把区间全改成0

(2)把区间全改成1

算比较简单的区间修改吧，不过这个 n 范围是 1e9 需要离散化一下，离散化之后用线段树每个点维护一个区间，不过注意要把r加一，因为如果 l == r 可能 find 之后 l > r ，而且区间也不好维护。所以加一就比较舒服了。

还要注意加上询问没涉及的区间长度。

让后这个题一看区间覆盖，直接拿珂朵莉试试能不能水过去。~~事实证明能水过去，还比线段树快100ms。~~

#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)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=600010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m,e;struct Query{ int l,r,k;}q[N];struct Node{ int l,r; int sum,val,lazy;}tr[N<<2];vector
                
                 v;int find(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin();}void pushup(int u){ tr[u].sum=tr[L].sum+tr[R].sum;}void pushdown(int u){ if(tr[u].lazy==1) tr[L].sum=tr[R].sum=0,tr[L].lazy=tr[R].lazy=1; else if(tr[u].lazy==2) tr[L].sum=tr[L].val,tr[R].sum=tr[R].val,tr[L].lazy=tr[R].lazy=2; tr[u].lazy=0;}void build(int u,int l,int r){ tr[u]={ l,r,0,0,0}; if(l==r) { tr[u].val=tr[u].sum=v[l+1]-v[l]; tr[u].lazy=0; printf("-%d\n",tr[u].val); return; } build(L,l,Mid),build(R,Mid+1,r); pushup(u); tr[u].val=tr[u].sum;}void modify(int u,int l,int r,int op){ if(tr[u].l>=l&&tr[u].r<=r) { tr[u].lazy=op; if(op==1) tr[u].sum=0; else tr[u].sum=tr[u].val; return; } pushdown(u); if(l<=Mid) modify(L,l,r,op); if(r>Mid) modify(R,l,r,op); pushup(u);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); cin>>n>>e; for(int i=1;i<=e;i++) { int l,r,z; scanf("%d%d%d",&l,&r,&z); r++; v.push_back(l),v.push_back(r); q[i]={ l,r,z}; } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); int ll=v.size(); build(1,0,ll-2); int ans=n-(v[ll-1]-1-v[0]+1); for(int i=1;i<=e;i++) { int l=q[i].l,r=q[i].r,z=q[i].k; l=find(l),r=find(r)-1; modify(1,l,r,z); printf("%d\n",ans+tr[1].sum); } return 0;}/**/

珂朵莉

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#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;#define IT set
                
                 ::iteratorint n,m;struct node{ int l,r; mutable LL val; node(int L,int R=-1,LL V=0):l(L),r(R),val(V) { } bool operator < (const node &w) const { return l
                 
                  s;IT split(int pos){ IT it=s.lower_bound(node(pos)); if(it!=s.end()&&it->l==pos) return it; it--; int L=it->l,R=it->r; LL V=it->val; s.erase(it); s.insert(node(L,pos-1,V)); return s.insert(node(pos,R,V)).first;}void assign_val(int l,int r,int val){ IT itr=split(r+1),itl=split(l),it=itl; for(;itl!=itr;itl++) n-=itl->val*(itl->r-itl->l+1); s.erase(it,itr); s.insert(node(l,r,val)); n+=(r-l+1)*val;}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d%d",&n,&m); s.insert(node(1,n,1)); while(m--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); if(k==1) assign_val(l,r,0); else assign_val(l,r,1); printf("%d\n",n); } return 0;}/**/

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

上一篇：Count on a tree 树上主席树

下一篇：Vases and Flowers HDU - 4614 线段树 + 二分

发表评论

关于作者

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

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章