题目 一直 0 pts,测了第一组数据的前一百行,没有问题。
#include<bits/stdc++.h>
#define int long long
#define PII pair< int, int >
using namespace std;
const int N = 2e5 + 5, mod = 998244353;
int n, tot, rt[5], a, b, c, cnt;
struct bds{
int fuhao, val;
} bdshi[N];
struct node{
int val, key, siz;
int lson, rson;
} t[N];
struct {
int New(int x){
t[++tot].val = x;
t[tot].key = 1ll * rand() * rand() % mod;
t[tot].siz = 1;
t[tot].lson = t[tot].rson = 0;
return tot;
}
void update(int x){
if (x == 0) return ;
t[x].siz = t[t[x].lson].siz + t[t[x].rson].siz + 1;
}
void split(int now, int &a, int &b, int k){
if (now == 0){
a = b = 0;
return ;
}
if (t[now].val <= k){
a = now;
split(t[now].rson, t[a].rson, b, k);
}
else {
b = now;
split(t[now].lson, a, t[b].lson, k);
}
update(now);
}
void merge(int &now, int a, int b){
if (a == 0 || b == 0){
now = a + b;
return ;
}
if (t[a].key >= t[b].key){
now = a;
merge(t[now].rson, t[a].rson, b);
}
else {
now = b;
merge(t[now].lson, a, t[b].lson);
}
update(now);
}
int query(int rt, int k){
int now = rt;
while(true){
if (k <= t[t[now].lson].siz) now = t[now].lson;
else if (k > t[t[now].lson].siz + 1){
k -= t[t[now].lson].siz + 1;
now = t[now].rson;
}
else return t[now].val;
}
}
} FHQ_treap[5];
template< typename T >inline void read(T &x){bool f=1;x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=(f?x:-x);return;}
template< typename T, typename ... L > void read(T &a , L && ... b) { read(a); read(b ...); }
int ksm(int a, int b, int p){int ans = 1;while(b){if(b & 1)ans =(ans*a)%p;b >>= 1;a = (a*a) % p;}return ans;}
signed main(){
// freopen("a.in", "r", stdin);
// freopen("a.out","w",stdout);
srand(time(0));
read(n);
while (n--){
string op;
cin >> op;
if (op == "Add"){
int x, y, z;
read(x, y, z);
z -= y;
if (x == 0){
if (y == z){
bdshi[++cnt].val = -200000001;
bdshi[cnt].fuhao = 2;
}
else {
bdshi[++cnt].val = 200000001;
bdshi[cnt].fuhao = 2;
}
continue;
}
else if (x > 0){
bdshi[++cnt].val = ceil((double)z / x) - 1;
bdshi[cnt].fuhao = 2;
// printf("%lld\n", bdshi[cnt].val);
// cout << "---------------2---------------" << '\n';
}
else {
bdshi[++cnt].val = floor((double)z / x) + 1;
bdshi[cnt].fuhao = 1;
// printf("%lld\n", bdshi[cnt].val);
// cout << "---------------1---------------" << '\n';
}
int now = FHQ_treap[bdshi[cnt].fuhao].New(bdshi[cnt].val);
FHQ_treap[bdshi[cnt].fuhao].split(rt[bdshi[cnt].fuhao], a, b, bdshi[cnt].val);
FHQ_treap[bdshi[cnt].fuhao].merge(a, a, now);
FHQ_treap[bdshi[cnt].fuhao].merge(rt[bdshi[cnt].fuhao], a, b);
}
if (op == "Del"){
int i;
read(i);
if (bdshi[i].val == 200000001 && bdshi[i].fuhao == 2) continue;
FHQ_treap[bdshi[i].fuhao].split(rt[bdshi[i].fuhao], a, b, bdshi[i].val);
FHQ_treap[bdshi[i].fuhao].split(a, a, c, bdshi[i].val - 1);
FHQ_treap[bdshi[i].fuhao].merge(c, t[c].lson, t[c].rson);
FHQ_treap[bdshi[i].fuhao].merge(rt[bdshi[i].fuhao], a, c);
FHQ_treap[bdshi[i].fuhao].merge(rt[bdshi[i].fuhao], rt[bdshi[i].fuhao], b);
bdshi[i].val = 200000001;
bdshi[i].fuhao = 2;
// printf("%lld %lld\n", i, bdshi[i].val);
}
if (op == "Query"){
int k;
read(k);
int dan = 0;
FHQ_treap[1].split(rt[1], a, b, k);
dan += t[b].siz;
// printf("%lld %lld\n", t[b].siz, t[b].val);
FHQ_treap[1].merge(rt[1], a, b);
FHQ_treap[2].split(rt[2], a, b, k - 1);
dan += t[a].siz;
FHQ_treap[2].merge(rt[2], a, b);
printf("%lld\n", dan);
}
}
return 0;
}