ZOJ 3324 Machine

线段树，延迟标记。

记录一下每个节点代表的区间的最小值，以及左右端点是否为最小值，记录区间被下压几次作为延迟标记，再记录一下这个区间中有多少个最小值的连通块。

$n$最大有$1$亿，可以开动态线段树避免离散化。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<ctime>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-;
void File()
{
    freopen("D:\\in.txt","r",stdin);
    freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
    char c = getchar();
    x = ;
    while(!isdigit(c)) c = getchar();
    while(isdigit(c))
    {
        x = x *  + c - '';
        c = getchar();
    }
}struct X
{
    int L,R;
    int Lson,Rson;
    int Min;
    bool A,B;
    int ans;
    int flag;
}s[];
int n,m,sz;int add(int ll,int rr)
{
    s[sz].L=ll; s[sz].R=rr;
    s[sz].Lson=s[sz].Rson=-;
    s[sz].Min=;
    s[sz].A=s[sz].B=;
    s[sz].ans=;
    s[sz].flag=;
    sz++;
    return sz-;
}void pushDown(int rt)
{
    int m=(s[rt].L+s[rt].R)/;
    if(s[rt].Lson==-) s[rt].Lson=add(s[rt].L,m);
    if(s[rt].Rson==-) s[rt].Rson=add(m+,s[rt].R);    if(s[rt].flag==) 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=;
}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!=&&s[s[rt].Rson].A!=) s[rt].ans--;
    }    else 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[rt].ans=s[s[rt].Lson].ans;
    }    else
    {
        s[rt].Min=s[s[rt].Rson].Min;
        s[rt].B=s[s[rt].Rson].B;
        s[rt].A=;
        s[rt].ans=s[s[rt].Rson].ans;
    }
}void update(int x,int L,int R,int rt)
{
    if(L<=s[rt].L&&s[rt].R<=R)
    {
        s[rt].flag+=x;
        s[rt].Min+=x;
        return ;
    }    pushDown(rt);    int m=(s[rt].L+s[rt].R)/;    if(L<=m) update(x,L,R,s[rt].Lson);
    if(R>m) update(x,L,R,s[rt].Rson);    pushUp(rt);
}int main()
{
    int T; scanf("%d",&T); int cas=;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("Case #%d:\n",cas++);        sz=; add(,n);        for(int i=;i<=m;i++)
        {
            char op[]; int L,R;
            scanf("%s%d%d",op,&L,&R); L++; R++;            if(op[]=='p') update(,L,R,);
            else update(-,L,R,);            if(s[].Min==) printf("%d\n",s[].ans);
            else printf("0\n");
        }
    }
    return ;
}