[CF 555C] Case of Chocolate

作法：

假設這次的詢問是$(x,y,L)$，那麼如果我們已經知道在第$1,...,x-1$行中每行的最上面那個被吃掉的格子座標的話，就可以算出答案了。對於$U$的詢問也一樣可以用類似的資料結構來做。但是$n$太大了，所以考慮先把輸入都離散化，這樣就可以用線段樹來做了：維護兩棵線段樹，並且當詢問$(x,y,L)$時（詢問為$U$時幾乎一模一樣），我們會需要在其中一棵線段樹中查詢「最大的$i$使得$i,...,x$中的最大值$\leq y$」的$i$，這顯然可以在$logn$的時間內做到，但我比賽時寫了二分搜答案的作法，複雜度多一個$log$，不至於TLE。查詢完後再去更新另一棵線段樹上的值就可以了。

另外也有不用線段樹的作法，詳細可以參考這篇，比線段樹的作法簡潔多了。

code :

#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
const int maxn=200000+10 ;
 
struct node
{
    node *l,*r ;
    int val ;
    node(int _v=INF){l=r=NULL ; val=_v ;}
};
void pull(node *u){u->val=min(u->l->val,u->r->val);}
node *build(int l,int r)
{
    if(l==r) return new node() ;
    node *u=new node() ;
    int mid=(l+r)/2 ;
    u->l=build(l,mid) ;
    u->r=build(mid+1,r) ;
    return u ;
}
void modify(int l,int r,node *u,int pos,int val)
{
    if(l==r){u->val=val ; return ;}
    int mid=(l+r)/2 ;
    if(pos<=mid) modify(l,mid,u->l,pos,val) ;
    else modify(mid+1,r,u->r,pos,val) ;
    pull(u) ;
}
int query(int l,int r,int L,int R,node *u)
{
    if(l==L && r==R) return u->val ;
    int mid=(L+R)/2 ;
    if(r<=mid) return query(l,r,L,mid,u->l) ;
    else if(l>mid) return query(l,r,mid+1,R,u->r) ;
    else return min(query(l,mid,L,mid,u->l),
                    query(mid+1,r,mid+1,R,u->r)) ;
}
 
void norm(vector<int> &v)
{
    sort(v.begin(),v.end()) ;
    v.resize(unique(v.begin(),v.end())-v.begin()) ;
}
int id(const vector<int> &v,int val)
{
    return lower_bound(v.begin(),v.end(),val)-v.begin() ;
}
 
set<int> s ;
int x[maxn],y[maxn],d[maxn] ;
vector<int> vx,vy ;
main()
{
    int n,q ; scanf("%d%d",&n,&q) ;
    vx.push_back(0) ; vy.push_back(0) ;
    for(int i=1;i<=q;i++)
    {
        char c[3] ; scanf("%d%d%s",&x[i],&y[i],c) ;
        d[i]=(c[0]=='L' ? 1 : 2) ;
        vx.push_back(x[i]) ;
        vy.push_back(y[i]) ;
    }
    norm(vx) ; norm(vy) ;
    int sz=vx.size() ;
    node *rx=build(0,sz-1) , *ry=build(0,sz-1) ;
    modify(0,sz-1,rx,0,0) ;
    modify(0,sz-1,ry,0,0) ;
    for(int i=1;i<=q;i++)
    {
        if(s.count(x[i])){printf("0\n") ; continue ;}
        s.insert(x[i]) ;
        if(d[i]==1)
        {
            int l=0 , r=id(vx,x[i]) , now=r ;
            while(r-l>1)
            {
                int mid=(r+l)/2 ;
                if(query(mid,now,0,sz-1,rx)<=y[i]) l=mid ;
                else r=mid ;
            }
            printf("%d\n",x[i]-vx[l]) ;
            modify(0,sz-1,ry,id(vy,y[i]),vx[l]) ;
        }
        else
        {
            int l=0 , r=id(vy,y[i]) , now=r ;
            while(r-l>1)
            {
                int mid=(r+l)/2 ;
                if(query(mid,now,0,sz-1,ry)<=x[i]) l=mid ;
                else r=mid ;
            }
            printf("%d\n",y[i]-vy[l]) ;
            modify(0,sz-1,rx,id(vx,x[i]),vy[l]) ;
        }
    }
}