耗氧代码求助
查看原帖
耗氧代码求助
394373
Hanoist楼主2021/6/10 12:46

我这个代码不开O2就全WA,开完就AC,求各位dalao帮助debug+解释QwQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define mid (l + r >> 1)
struct wyx{
	long long laz,ls,rs,mx,lr;
}tre[400001];
struct zwy{
	long long len,dep,id;
}p[200001];
struct yjx{
	wyx update(wyx x,wyx y){
		wyx z;
		z.lr = x.lr + y.lr;
        z.ls = x.ls,z.rs = y.rs;
        if(x.lr == x.mx) z.ls += y.ls;
        if(y.lr == y.mx) z.rs += x.rs;
        z.mx = max(x.mx,max(y.mx,x.rs + y.ls));
        return z;
	}
    void push(int k){
        if(!tre[k].laz) return;
        tre[k << 1].laz = tre[k << 1 | 1].laz = tre[k].laz;
        if(tre[k].laz == 1){
            tre[k << 1].mx = tre[k << 1].ls = tre[k << 1].rs = 0;
            tre[k << 1 | 1].mx = tre[k << 1 | 1].ls = tre[k << 1 | 1].rs = 0;
        }
        else{
            tre[k << 1].mx = tre[k << 1].ls = tre[k << 1].rs = tre[k << 1].lr;
            tre[k << 1 | 1].mx = tre[k << 1 | 1].ls = tre[k << 1 | 1].rs = tre[k << 1 | 1].lr;
        }
        tre[k].laz = 0;
    }
    void build(int k,int l,int r){
        if(l == r){
            tre[k].laz = 0;
            tre[k].ls = tre[k].rs = tre[k].mx = tre[k].lr = 1;
            return;
        }
        build(k << 1,l,mid);
        build(k << 1 | 1,mid + 1,r);
        tre[k] = update(tre[k << 1],tre[k << 1 | 1]);
    }
    void modify(int k,int l,int r,int x,int y,int c){
        push(k);
        if(x <= l && r <= y){
            if(c == 1) tre[k].ls = tre[k].rs = tre[k].mx = 0;
            else tre[k].ls = tre[k].rs = tre[k].mx = tre[k].lr;
            tre[k].laz = c;
            return;
        }
        if(x <= mid) modify(k << 1,l,mid,x,y,c);
        if(y > mid) modify(k << 1 | 1,mid + 1,r,x,y,c);
        tre[k] = update(tre[k << 1],tre[k << 1 | 1]);
    }
    int query(int k,int l,int r,int c){
        push(k);
        if(l == r) return l;
        if(tre[k << 1].mx >= c) return query(k << 1,l,mid,c);
        if(tre[k << 1].rs + tre[k << 1 | 1].ls >= c) return mid - tre[k << 1].rs + 1;
        return query(k << 1 | 1,mid + 1,r,c);
    }
}STr;
int main(){
    int i,m,n,w,x,y,z,temp;
    scanf("%d %d",&n,&m);
	STr.build(1,1,n);
    for(i = 1;i <= m;i++){
		scanf("%d",&z);
        if(z == 1){
            scanf("%d",&x);
            if(tre[1].mx >= x){
                temp = STr.query(1,1,n,x);
                printf("%d\n",temp);
                STr.modify(1,1,n,temp,temp + x - 1,1);
            }
            else printf("0\n");
        }
        if(z == 2){
            scanf("%d %d",&x,&y);
            STr.modify(1,1,n,x,x + y - 1,2);
        }
	}
    return 0;
}
2021/6/10 12:46
加载中...