第一次: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