不是 tlqtj

本人使用 bit 套 multiset，个人认为是 $\mathcal{O}(n\log^2 n)$，但是又看到数据水，可能写假了。

Submission

还有题解里貌似没有这种做法，可不可以添加qwq（只有我这种蒟蒻才会一眼树套树罢。）

#include<bits/stdc++.h>
#define N 100005
#define mp make_pair
using namespace std;
int n,l,r;
char op;
multiset<pair<int,int>>bit[N];
vector<pair<int,int>>a;
void insert(int x,int k){
    for(int i=x;i<=1e5;i+=i&(-i)){
        bit[i].insert(mp(k,x));
    }
}
void erase(int x,int k){
    for(int i=x;i<=1e5;i+=i&(-i)){
        bit[i].erase(mp(k,x));
    }
}
int query(int x,int l,int r){
    a.clear();
    for(int i=x;i;i-=i&(-i)){
        for(auto j=bit[i].lower_bound(mp(l,0));j!=bit[i].end();++j){
            a.emplace_back(j->first,j->second);
        }
    }
    for(auto[qr,ql]:a){
        erase(ql,qr);
    }
    return a.size();
}
int size(int x){
    int ret=0;
    for(int i=x;i;i-=i&(-i)){
        ret+=bit[i].size();
    }
    return ret;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n;
    while(n--){
        cin>>op;
        if(op^'B'){
            cin>>l>>r;
            cout<<query(r,l,r)<<'\n';
            insert(l,r);
        }else{
            cout<<size(1e5)<<'\n';
        }
    }
}