本文共 1949 字，大约阅读时间需要 6 分钟。
线段树，延迟标记。
记录一下每个节点代表的区间的最小值，以及左右端点是否为最小值，记录区间被下压几次作为延迟标记，再记录一下这个区间中有多少个最小值的连通块。
$n$最大有$1$亿，可以开动态线段树避免离散化。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-10;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}struct X{ int L,R; int Lson,Rson; int Min; bool A,B; int ans; int flag;}s[420000];int n,m,sz;int add(int ll,int rr){ s[sz].L=ll; s[sz].R=rr; s[sz].Lson=s[sz].Rson=-1; s[sz].Min=0; s[sz].A=s[sz].B=1; s[sz].ans=1; s[sz].flag=0; sz++; return sz-1;}void pushDown(int rt){ int m=(s[rt].L+s[rt].R)/2; if(s[rt].Lson==-1) s[rt].Lson=add(s[rt].L,m); if(s[rt].Rson==-1) s[rt].Rson=add(m+1,s[rt].R); if(s[rt].flag==0) return; s[s[rt].Lson].flag+=s[rt].flag; s[s[rt].Lson].Min+=s[rt].flag; s[s[rt].Rson].flag+=s[rt].flag; s[s[rt].Rson].Min+=s[rt].flag; s[rt].flag=0;}void pushUp(int rt){ if(s[s[rt].Lson].Min==s[s[rt].Rson].Min) { s[rt].Min=s[s[rt].Lson].Min; s[rt].A=s[s[rt].Lson].A; s[rt].B=s[s[rt].Rson].B; s[rt].ans=s[s[rt].Lson].ans+s[s[rt].Rson].ans; if(s[s[rt].Lson].B!=0&&s[s[rt].Rson].A!=0) s[rt].ans--; } else if(s[s[rt].Lson].Min m) update(x,L,R,s[rt].Rson); pushUp(rt);}int main(){ int T; scanf("%d",&T); int cas=1; while(T--) { scanf("%d%d",&n,&m); printf("Case #%d:\n",cas++); sz=0; add(1,n); for(int i=1;i<=m;i++) { char op[5]; int L,R; scanf("%s%d%d",op,&L,&R); L++; R++; if(op[0]=='p') update(1,L,R,0); else update(-1,L,R,0); if(s[0].Min==0) printf("%d\n",s[0].ans); else printf("0\n"); } } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/6363464.html