9RE,1WA,求调(线段树)
查看原帖
9RE,1WA,求调(线段树)
1417453
chenzhishuo2012楼主2024/11/7 16:41

不知道哪里写挂了,感觉看上去没啥错,还请大佬帮忙调一下

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define inf 0x3f3f3f3f3f3f3f3f
#define LOCAL
using namespace std;
namespace ly{
    namespace IO{
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar()(p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush()(fwrite(out,1,p3-out,stdout))
            #define putchar(x)(p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
            namespace usr{
                template<typename type>
                inline type read(type&x){
                    x=0;bool flag(0);char ch=getchar();
                    while(!isdigit(ch))flag^=ch=='-',ch=getchar();
                    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                    return flag?x=-x:x;
                }
                template<typename type>
                inline void write(type x){
                    x<0?x=-x,putchar('-'):0;
                    static short Stack[50],top(0);
                    do Stack[++top]=x%10,x/=10;while(x);
                    while(top)putchar(Stack[top--]|48);
                }
                inline char read(char&x){do x=getchar();while(isspace(x));return x;}
                inline char write(const char&x){return putchar(x);}
                inline void read(char*x){static char ch;read(ch);do*(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
                template<typename type>inline void write(type*x){while(*x)putchar(*(x++));}
                inline void read(string&x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
                inline void write(const string&x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
                template<typename type,typename...T>inline void read(type&x,T&...y){read(x),read(y...);}
                template<typename type,typename...T>
                inline void write(const type&x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
                template<typename type>
                inline void put(const type&x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
            }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }
    using namespace IO::usr;
}
using namespace ly::IO::usr;
#define ls(p) p<<1
#define rs(p) p<<1|1
int l,n,opt,a,b,c,d;
struct tree{
    int t[40010],lazy[40010],ans;
    tree(){
        ans=0;
        memset(t,0,sizeof(t));
        memset(lazy,0,sizeof(lazy));
    }
    void pushup(int p){
        t[p]=t[ls(p)]+t[rs(p)];
    }
    void pushdown(int p,int l,int r){
        if(lazy[p]==1){
            int mid=(l+r)/2;
            lazy[ls(p)]=lazy[rs(p)]=1;
            t[ls(p)]=mid-l+1;
            t[rs(p)]=r-mid;
        }
        if(lazy[p]==-1){
            lazy[ls(p)]=lazy[rs(p)]=-1;
            t[ls(p)]=t[rs(p)]=0;
        }
        lazy[p]=0;
    }
    void build(int l,int r,int p){
        if(l==r){
            t[p]=1;
            return;
        }
        int mid=(l+r)/2;
        build(l,mid,ls(p));
        build(mid+1,r,rs(p));
        pushup(p);
    }
    void modify1(int l,int r,int L,int R,int p){
        if(L<=l&&R>=r){
            ans+=t[p];
            lazy[p]=-1;
            t[p]=0;
            return;
        }
        int mid=(l+r)/2;
        pushdown(p,l,r);
        if(L<=mid)modify1(l,mid,L,R,ls(p));
        if(R>mid)modify1(mid+1,r,L,R,rs(p));
        pushup(p);
    }
    void modify2(int l,int r,int L,int R,int p){
        if(L<=l&&R>=r){
            lazy[p]=1;
            t[p]=r-l+1;
            return;
        }
        int mid=(l+r)/2;
        pushdown(p,l,r);
        if(L<=mid)modify2(l,mid,L,R,ls(p));
        if(R>mid)modify2(mid+1,r,L,R,rs(p));
        pushup(p);
    }
}tr[2];
signed main(){
    read(l,n);
    l++;
    tr[0].build(1,l,1);
    tr[1].build(1,l,1);
    for(int i=1;i<=n;i++){
        read(opt);
        if(opt==0){
            read(a,b);
            a++;
            b++;
            tr[0].modify1(1,n,a,b,1);
            tr[1].modify1(1,n,a,b,1);
        }
        else{
            read(c,d);
            c++;
            d++;
            tr[0].modify2(1,n,c,d,1);
        }
    }
    put(tr[0].t[1]-tr[1].t[1]);
    put(tr[0].ans-tr[1].ans);
    return 0;
}
2024/11/7 16:41
加载中...