这题我是用动态开点线段树做的,7,8,9,10 这四个大 的测试点全部 WA 掉了,简单的对了一下大测试点,没找到错误在哪,求大神帮忙看一下哪里错了或者造一组 hack 数据。
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int SIZE(1<<21);
namespace Fread{char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T){return '\n';}}return *S++;}}
namespace Fwrite{char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T){flush();}}struct NTR{~NTR(){flush();}}ztr;}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace CCF_NB{
#define ll long long
#define ss stable_sort
#define inf 50000000
#define umap unordered_map
#pragma GCC opitimize(2)
#pragma GCC opitimize(3)
inline void read(string &str){char s=getchar();while(s==' '||s=='\n'||s=='\r'){s=getchar();}while(s!=' '&&s!='\n'&&s!='\r'){str+=s;s=getchar();}}
inline void read(char &_c){_c=getchar();while(_c==' '||_c=='\n'||_c=='\r') _c=getchar();}
inline void read(double &_d){scanf("%lf",&_d);}
inline void write(string _str){printf("%s",_str.c_str());}
inline void write(char _c){putchar(_c);}
inline void write(double _d){printf("%f",_d);}
template <typename T> inline void read(T& x){x=0;T f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=x*f;return;}
template <typename T,typename ...Arg>inline void read(T& x,Arg& ...arg){read(x);read(arg...);}
template <typename T>inline void write(T x){if(x<0)putchar('-'),x=-x;if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}
template <typename T,typename ...Arg>inline void write(T x,Arg ...arg){write(x);write(arg...);}
template <typename T>inline T _get(){T _____;read(_____);return _____;}
template <typename T>inline T gcd(T x,T y){return __gcd(x,y);}
template <typename T,typename ...Arg>inline T gcd(T x,Arg ...arg){return gcd(x,gcd(arg...));}
}
using namespace CCF_NB;
struct node{
int ls,rs,sum,maxn,minn;
}tree[50000005];
void up(int rt){
tree[rt].sum=tree[tree[rt].ls].sum+tree[tree[rt].rs].sum;
tree[rt].maxn=max(tree[tree[rt].ls].sum?tree[tree[rt].ls].maxn:0,tree[tree[rt].rs].sum?tree[tree[rt].rs].maxn:0);
tree[rt].minn=min(tree[tree[rt].ls].sum?tree[tree[rt].ls].minn:inf,tree[tree[rt].rs].sum?tree[tree[rt].rs].minn:inf);
}
int cnt=1;
void Insert(int &rt,int l,int r,int x){
if(!rt) rt=++cnt;
// write(rt,' ',l,' ',r,' ',x,'\n');
if(l==r){
tree[rt].sum++;
tree[rt].maxn=x;
tree[rt].minn=x;
return ;
}
int mid=(l+r)/2;
if(x<=mid) Insert(tree[rt].ls,l,mid,x);
else Insert(tree[rt].rs,mid+1,r,x);
up(rt);
}
void Delete(int rt,int l,int r,int x){
// write(rt,' ',l,' ',r,' ',x,'\n');
if(l==r){
tree[rt].sum--;
return ;
}
int mid=(l+r)/2;
if(x<=mid) Delete(tree[rt].ls,l,mid,x);
else Delete(tree[rt].rs,mid+1,r,x);
up(rt);
}
int ask1(int rt,int l,int r,int L,int R){
// write(rt,' ',l,' ',r,' ',L,' ',R,'\n');
if(l>=L&&r<=R) return tree[rt].sum;
int mid=(l+r)/2,sum=0;
if(L<=mid&&tree[rt].ls) sum+=ask1(tree[rt].ls,l,mid,L,R);
if(mid<R&&tree[rt].rs) sum+=ask1(tree[rt].rs,mid+1,r,L,R);
return sum;
}
int ask2(int rt,int l,int r,int rk){
if(l==r) return l;
int mid=(l+r)/2;
if(tree[rt].ls&&rk<=tree[tree[rt].ls].sum) return ask2(tree[rt].ls,l,mid,rk);
else return ask2(tree[rt].rs,mid+1,r,rk-tree[tree[rt].ls].sum);
}
int ask3(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R) return tree[rt].maxn;
int mid=(l+r)/2,ans1=0,ans2=0;
if(L<=mid&&tree[rt].ls) ans1=ask3(tree[rt].ls,l,mid,L,R);
if(mid<R&&tree[rt].rs) ans2=ask3(tree[rt].rs,mid+1,r,L,R);
return max(ans1,ans2);
}
int ask4(int rt,int l,int r,int L,int R){
if(l>=L&&r<=R) return tree[rt].minn;
int mid=(l+r)/2,ans1=inf,ans2=inf;
if(L<=mid&&tree[rt].ls) ans1=ask4(tree[rt].ls,l,mid,L,R);
if(mid<R&&tree[rt].rs) ans2=ask4(tree[rt].rs,mid+1,r,L,R);
return min(ans1,ans2);
}
int n,CONST_NUM=1;
int main(){
read(n);
while(n--){
int x,y;
read(x,y);
y+=10000000;
switch(x){
case 1:Insert(CONST_NUM,0,2e7,y);break;
case 2:Delete(CONST_NUM,0,2e7,y);break;
case 3:write(ask1(CONST_NUM,0,2e7,0,y-1)+1,'\n');break;
case 4:write(ask2(CONST_NUM,0,2e7,y-10000000)-10000000,'\n');break;
case 5:write(ask3(CONST_NUM,0,2e7,0,y-1)-10000000,'\n');break;
case 6:write(ask4(CONST_NUM,0,2e7,y+1,2e7)-10000000,'\n');break;
}
}
return 0;
}
大号莫名其妙的没法发,用小号发一下。