codeforces 343d-白红宇

codeforces 343d

阅读量：5144 次

发布时间：2019-06-13

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

题意：一棵树结构上有水，往一个节点加水，那么所有的子节点都会有水，或者排干一个节点的水，那么它的上面的节点都会没水。

用dfs序，数组记录区间内全部有水为1，区间内有没水的点就为0。

倒水：区间更新，排水：单点更新，并更新途中经过的所有点，查询：区间查询。

倒水：区间内所有的点变为有水，就是1，用lazy数组，要下传。

排水：所有节点的dfs序之间的相交只能是包含，并且只被祖先包含。那么在线段树中就将经过的点全部排去。这样祖先节点查询时就为0了，并且无关节点还是有水。不过这样有个BUG，假如开始全有水，如果一个节点排空了立即加水，那么祖先又有水了，实际上是没水，这时将祖先排水就行。

62 13 14 14 52 641 12 41 43 1就这。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define mkp make_pairusing namespace std;const double EPS=1e-8;typedef long long lon;const lon SZ=500010,SSZ=10*SZ,APB=20,INF=0x7FFFFFFF,mod=1000000007;lon n,bg[SZ],fn[SZ],cnt,arr[SSZ],lazy[SSZ];lon pre[SZ];vector
                   
                     mp[SZ];void release(){ }void dfs(int x,int p){ bg[x]=++cnt; pre[x]=p; for(int i=0;i
                    
                     rr)return; if(ql<=mid)update(ll,mid,rt*2,ql,qr); if(qr>mid)update(mid+1,rr,rt*2+1,ql,qr); pushup(rt);}void update(int ll,int rr,int rt,int pos){ int mid=(ll+rr)/2; pushdown(rt); if(ll==rr) { arr[rt]=0; return; } if(pos<=mid)update(ll,mid,rt*2,pos); else update(mid+1,rr,rt*2+1,pos); pushup(rt);}int qry(int ll,int rr,int rt,int ql,int qr){ //cout<<" "<
                     
                      <<" "<
                      
                       <
                       
                        rr)return 1; int res1=1,res2=1; if(ql<=mid)res1=qry(ll,mid,rt*2,ql,qr); if(qr>mid)res2=qry(mid+1,rr,rt*2+1,ql,qr); return res1*res2;}void init(){ cin>>n; for(int i=1;i<=n-1;++i) { int a,b; cin>>a>>b; mp[a].push_back(b); mp[b].push_back(a); } dfs(1,-1);}void work(){ int qnum; cin>>qnum; for(int i=1;i<=qnum;++i) { int type,x; cin>>type>>x; if(type==1) { if(x!=1&&!qry(1,cnt,1,bg[x],fn[x]))update(1,cnt,1,bg[pre[x]]); update(1,cnt,1,bg[x],fn[x]); } else if(type==2) { update(1,cnt,1,bg[x]); } else { //cout<<"3: "<
                        
                         <<" "<
                         
                          <
                          
                           >casenum; //cout<
                           
                            <

转载于:https://www.cnblogs.com/gaudar/p/10698052.html

你可能感兴趣的文章

android%3cspan,Microsoft 365 Apps update channel name changes: iOS, Mac, and Android