求助
查看原帖
求助
732194
cjsyc楼主2022/6/14 20:35

这题我是用动态开点线段树做的,7788991010 这四个大 的测试点全部 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;
}

大号莫名其妙的没法发,用小号发一下。

2022/6/14 20:35
加载中...