Santa Claus 2 （st表的lower_bound用法）

题目链接：Santa Claus 2

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
#define fi first 
#define se second
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 2e5+5;
int n,m,sx,sy;
int dx[] = {0,0,1,-1};//U D R L
int dy[] = {1,-1,0,0};
map<int,set<int>>stx;
map<int,set<int>>sty;
map<pair<int,int>,int>mp;

void solve(){
    cin>>n>>m>>sx>>sy;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        stx[x].insert(y);
        sty[y].insert(x);
    }

    int nx = sx;
    int ny = sy;
    int ans = 0;

    for(int i=1;i<=m;i++){
        char op;cin>>op;
        int d;cin>>d;
        if(op == 'U'){
            auto be = stx[nx].lower_bound(ny);
            auto ed = stx[nx].upper_bound(ny + d);
            vector<int>vec;
            for(auto it = be ; it != ed ; it++){
                if(!mp[{nx , *it}]){
                    vec.push_back(*it);
                    mp[{nx , *it}] = 1;
                    ans++;

                }
            }
            for(auto &y:vec){
                stx[nx].erase(y);
            }
            ny += d;
        }
        else if(op == 'D'){
            auto be = stx[nx].lower_bound(ny - d);
            auto ed = stx[nx].upper_bound(ny);
            vector<int>vec;
            for(auto it = be ; it != ed ; it++){
                if(!mp[{nx , *it}]){
                    vec.push_back(*it);
                    mp[{nx , *it}] = 1;
                    ans++;
                }
            }
            for(auto &y:vec){
                stx[nx].erase(y);
            }
            ny -= d;

        }
        else if(op == 'R'){
            auto be = sty[ny].lower_bound(nx);
            auto ed = sty[ny].upper_bound(nx + d);
            vector<int>vec;
            for(auto it = be ; it != ed ; it++){
                if(!mp[{*it , ny}]){
                    vec.push_back(*it);
                    mp[{*it , ny}] = 1;
                    //cout<<(*it)<<" "<<ny<<"\n";
                    ans++;
                }
            }
            for(auto &y:vec){
                sty[ny].erase(y);
            }
            nx += d;
        }
        else{
            auto be = sty[ny].lower_bound(nx - d);
            auto ed = sty[ny].upper_bound(nx);
            vector<int>vec;
            for(auto it = be ; it != ed ; it++){
                if(!mp[{*it , ny}]){
                    //cout<<sty[ny].count(*it)<<"\n";
                    //sty[ny].erase(*it);
                    vec.push_back(*it);
                    mp[{*it , ny}] = 1;
                    //cout<<(*it)<<" "<<ny<<"\n";
                    ans++;
                }
            }
            for(auto &y:vec){
                sty[ny].erase(y);
            }
            nx -= d;
        }
    }

    cout<<nx<<" "<<ny<<" "<<ans<<"\n";
    
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}