同样的代码评测结果不一样。。。
查看原帖
同样的代码评测结果不一样。。。
565945
Azure__楼主2022/7/2 17:55

第一次:WA这里
第二次:MLE这里
题解中数组1.5e7没问题,但我第二次提交就MLE,希望大佬们能帮忙解释一下,可以的话帮本蒟蒻改改。代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,root;
struct node{
    int l,r,w,f,size;
} tree[15000001];
inline int read(){
    char c; int x=0,f=1; c=getchar();
    while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }
    while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
    return x*f;
}
inline void push_up(int k){
	tree[k].w=tree[tree[k].l].w+tree[tree[k].r].w;
}
inline int build(){
	tree[++cnt].w=0; tree[cnt].f=-1;
	tree[cnt].l=0; tree[cnt].r=0;
	return cnt;
}
inline void push_down(int k,int l,int r){
	if(tree[k].f==1){
    	tree[tree[k].l].w=tree[tree[k].l].size*1;
    	tree[tree[k].r].w=tree[tree[k].r].size*1;
    	tree[tree[k].l].f=1;
    	tree[tree[k].r].f=1;
    	tree[k].f=-1;
    }
    if(tree[k].f==0){
    	tree[tree[k].l].w=0;
    	tree[tree[k].r].w=0;
    	tree[tree[k].l].f=0;
    	tree[tree[k].r].f=0;
    	tree[k].f=-1;
   }
}
inline void insert(int l,int r,int k,int ind,int x){
	++tree[k].size;
	if(l==r){
		tree[k].w=x; return;
	}
	int mid=(l+r)>>1;
	if(ind<=mid){
		if(!tree[k].l) tree[k].l=build();
		insert(l,mid,tree[k].l,ind,x);
	}
	else{
		if(!tree[k].r) tree[k].r=build();
		insert(mid+1,r,tree[k].r,ind,x);
	}
	push_up(k);
}
inline void change_interval(int k,int l,int r,int a,int b,int y){
	if(l>=a&&r<=b){
		tree[k].w=tree[k].size*y;
		tree[k].f=y;
		return;
	}
	if(tree[k].f!=-1) push_down(k,l,r);
	int mid=(l+r)>>1;
	if(a<=mid){
		if(!tree[k].l) tree[k].l=build();
		change_interval(tree[k].l,l,mid,a,b,y);
	}
	if(b>mid){
		if(!tree[k].r) tree[k].r=build();
		change_interval(tree[k].r,mid+1,r,a,b,y);
	}
	push_up(k);
}
int main()
{
	n=read(); m=read();
	root=build();
	for(int i=1;i<=n;i++){
		insert(1,n,root,i,0);
	}
	while(m--){
		int x=read(),y=read(),t=read();
		if(t==1) change_interval(1,1,n,x,y,1);
		if(t==2) change_interval(1,1,n,x,y,0);
		printf("%d\n",n-tree[1].w);
	}
	return 0;
}
```cpp
2022/7/2 17:55
加载中...