[POI 20 Stage 2] Watering can

作法：

建一個可以區間加值和區間查詢最大值與最大值位置的線段樹，作法是每次就直接對要加值的區間加值，然後對那個區間查詢最大值，如果最大值 >= k ，那麼在之後他就永遠會 >= k 了，所以可以直接把他調成負無限大，並把他標記起來。重複這個步驟直到最大值 < k 為止。並且再用另外一棵線段樹紀錄一個區間裡面已經有幾個數被標記了，就可以對他做查詢了。

code :

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int maxn=300000+10 ;
 
struct P{int val,tag,id;}ST[4*maxn];
struct RET{int val,id;};
int ST2[4*maxn] ;
 
int n,k,a[maxn] ;
 
void pull(int id)
{
     ST[id].val = max(ST[2*id].val,ST[2*id+1].val) ;
     if(ST[2*id].val > ST[2*id+1].val) ST[id].id=ST[2*id].id ;
     else ST[id].id=ST[2*id+1].id ;
}
 
void push(int id)
{
     if(!ST[id].tag) return ;
     int t=ST[id].tag ;
     ST[2*id].val+=t ; ST[2*id].tag+=t ;
     ST[2*id+1].val+=t ; ST[2*id+1].tag+=t ;
     ST[id].tag=0 ;
}
 
void build(int l,int r,int id)
{
     if(l==r) { ST[id]=(P){a[l],0,l} ; return ; }
     int mid=(l+r)/2 ;
     build(l,mid,2*id) ;
     build(mid+1,r,2*id+1) ;
     pull(id) ;
}
 
void add(int l,int r,int L,int R,int id,int val)
{
     if(l==L && r==R) { ST[id].val+=val ; ST[id].tag+=val ; return ; }
     push(id) ;
     int mid=(L+R)/2 ;
     if(r<=mid) add(l,r,L,mid,2*id,val) ;
     else if(l>mid) add(l,r,mid+1,R,2*id+1,val) ;
     else add(l,mid,L,mid,2*id,val) ,
          add(mid+1,r,mid+1,R,2*id+1,val) ;
     pull(id) ;
}
 
RET cal(const RET &x,const RET &y)
{
     RET r ;
     r.val=max(x.val,y.val) ;
     if(x.val > y.val) r.id=x.id ;
     else r.id=y.id ;
     return r ;
}
 
RET query(int l,int r,int L,int R,int id)
{
     if(l==L && r==R) return (RET){ST[id].val,ST[id].id} ;
     int mid=(L+R)/2 ;
     if(r<=mid) return query(l,r,L,mid,2*id) ;
     else if(l>mid) return query(l,r,mid+1,R,2*id+1) ;
     else return cal(query(l,mid,L,mid,2*id),
                     query(mid+1,r,mid+1,R,2*id+1)) ;
}
 
void modify2(int L,int R,int id,int pos)
{
     if(L==R) { ST2[id]++ ; return ; }
     int mid=(L+R)/2 ;
     if(pos<=mid) modify2(L,mid,2*id,pos) ;
     else modify2(mid+1,R,2*id+1,pos) ;
     ST2[id]++ ;
}
 
int query2(int l,int r,int L,int R,int id)
{
     if(l==L && r==R) return ST2[id] ;
     int mid=(L+R)/2 ;
     if(r<=mid) return query2(l,r,L,mid,2*id) ;
     else if(l>mid) return query2(l,r,mid+1,R,2*id+1) ;
     else return query2(l,mid,L,mid,2*id)+query2(mid+1,r,mid+1,R,2*id+1) ;
}
 
void inicjuj(int N,int K,int *D)
{
     n=N ; k=K ;
     for(int i=1;i<=n;i++) a[i]=D[i-1] ;
     build(1,n,1) ;
     while(1)
     {
          RET tmp=query(1,n,1,n,1) ;
          if(tmp.val < k) break ;
          modify2(1,n,1,tmp.id) ;
          add(tmp.id,tmp.id,1,n,1,-INF) ;
     }
}
 
void podlej(int l,int r)
{
     l++ ; r++ ;
     add(l,r,1,n,1,1) ;
     while(1)
     {
          RET tmp=query(l,r,1,n,1) ;
          if(tmp.val < k) break ;
          modify2(1,n,1,tmp.id) ;
          add(tmp.id,tmp.id,1,n,1,-INF) ;
     }
}
 
int dojrzale(int l,int r)
{
     return query2(l+1,r+1,1,n,1) ;
}