inline int read(){int f=1,c=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}return f*c;}
inline void write(int x){if (x <0)putchar('-'),x= -x;if(x > 9)write(x / 10);putchar(x % 10 + '0');return;}
void pushup(int id){s[id]=s[ls[id]]+s[rs[id]];}
void pushdown(int id,int l,int r){
if(lazy[id]==-1)return;
if(!ls[id])ls[id]=++cnt;
if(!rs[id])rs[id]=++cnt;
int mid=((l+r)>>1);
s[ls[id]]=lazy[id]*(mid-l+1);s[rs[id]]=lazy[id]*(r-mid);lazy[ls[id]]=lazy[rs[id]]=lazy[id];lazy[id]=-1;
}
void updata(int &id,int l,int r,int x,int y,int k){
if(!id)id=++cnt;
if(x<=l&&y>=r){s[id]=k*(r-l+1);lazy[id]=k;return;}
int mid=((l+r)>>1);
pushdown(id,l,r);
if(x<=mid)updata(ls[id],l,mid,x,y,k);
if(y>mid)updata(rs[id],mid+1,r,x,y,k);
pushup(id);
}
int l,r,opt;
signed main(){
memset(lazy,-1,sizeof lazy);
n=read();q=read();
while(q--){
l=read(),r=read(),opt=read();
if(opt==1)updata(base,1,n,l,r,1);
else updata(base,1,n,l,r,0);
write(n-s[base]);
putchar('\n');
}
}
这样直接TLE
#include<stdio.h>
#include<string.h>
using namespace std;
const int N = 15000005;
int base;
int cnt;
int n,q;
int ls[N];
int rs[N];
int s[N];
int lazy[N];
inline int read()
{
int f=1,c=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}
return f*c;
}
inline void write(int x)
{
if (x < 0) putchar('-'), x = -x;
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
return;
}
inline void pushup(int id){
s[id]=s[ls[id]]+s[rs[id]];
}
inline void pushdown(int id,int l,int r){
if(lazy[id]==-1)return;
if(!ls[id])ls[id]=++cnt;
if(!rs[id])rs[id]=++cnt;
int mid=((l+r)>>1);
s[ls[id]]=lazy[id]*(mid-l+1);
s[rs[id]]=lazy[id]*(r-mid);
lazy[ls[id]]=lazy[rs[id]]=lazy[id];
lazy[id]=-1;
}
inline void updata(int &id,int l,int r,int x,int y,int k){
if(!id)id=++cnt;
if(x<=l&&y>=r){
s[id]=k*(r-l+1);
lazy[id]=k;
return;
}
int mid=((l+r)>>1);
pushdown(id,l,r);
if(x<=mid)updata(ls[id],l,mid,x,y,k);
if(y>mid)updata(rs[id],mid+1,r,x,y,k);
pushup(id);
}
int l,r,opt;
signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(nullptr);
memset(lazy,-1,sizeof lazy);
n=read();
q=read();
while(q--){
l=read(),r=read(),opt=read();
if(opt==1)updata(base,1,n,l,r,1);
else updata(base,1,n,l,r,0);
write(n-s[base]);
putchar('\n');
}
}
给函数全套上inline就过了,敬爱的CF同志,我认为这并不好笑