题目描述

题解

比赛时的想法：离线，把相关的区间找出来，再向下拓展一个儿子以便向上合并，然后维护区间是否全满

吹风等于把y翻转

主席树，每次吹风时只维护源线段树，单点修改时复制整棵树，每棵树维护区间最小方便二分，修改就是改成0或y

比较好写

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define file
using namespace std;

int tr[25000001][3],c[1000001],t[1000001],rt[1000001],d[1000001][2],n,m,Q,i,j,k,l,len,T,Find,tot,x,y;
bool Bz,Find2;
char st[7],ch;

void Read(int &x)
{
    x=0;
    
    ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+(ch-'0'),ch=getchar();
}

void copy(int t)
{
    ++len;
    tr[len][0]=tr[t][0];
    tr[len][1]=tr[t][1];
    tr[len][2]=tr[t][2];
}

void New(int t,int x)
{
    copy(tr[t][x]);
    tr[t][x]=len;
}

void mt(int t,int l,int r)
{
    int mid=(l+r)/2;
    
    len=max(len,t);
    if (l==r) {tr[t][2]=c[l];return;}
    
    tr[t][0]=t*2;
    tr[t][1]=t*2+1;
    
    mt(tr[t][0],l,mid);
    mt(tr[t][1],mid+1,r);
    
    tr[t][2]=min(tr[tr[t][0]][2],tr[tr[t][1]][2]);
}

void change(int t,int l,int r,int x,int s)
{
    int mid=(l+r)/2;
    
    if (l==r) {tr[t][2]=s;return;}
    
    if (x<=mid)
    New(t,0),change(tr[t][0],l,mid,x,s);
    else
    New(t,1),change(tr[t][1],mid+1,r,x,s);
    
    tr[t][2]=min(tr[tr[t][0]][2],tr[tr[t][1]][2]);
}
void findu(int T,int t,int l,int r,int x)
{
    int mid=(l+r)/2;
    
    if (l==r) {if (tr[t][2]>=T) Find=l; else Find2=1;return;}
    
    if (x<r)
    {
        if (mid<x)
        findu(T,tr[t][1],mid+1,r,x);
        if (!Find2)
        findu(T,tr[t][0],l,mid,x);
    }
    else
    {
        if (tr[t][2]>=T)
        Find=l;
        else
        {
            if (tr[tr[t][1]][2]>=T)
            Find=mid+1,findu(T,tr[t][0],l,mid,x);
            else
            findu(T,tr[t][1],mid+1,r,x);
        }
    }
}
void findd(int T,int t,int l,int r,int x)
{
    int mid=(l+r)/2;
    
    if (l==r) {if (tr[t][2]>=T) Find=l; else Find2=1;return;}
    
    if (l<x)
    {
        if (x<=mid)
        findd(T,tr[t][0],l,mid,x);
        if (!Find2)
        findd(T,tr[t][1],mid+1,r,x);
    }
    else
    {
        if (tr[t][2]>=T)
        Find=r;
        else
        {
            if (tr[tr[t][0]][2]>=T)
            Find=mid,findd(T,tr[t][1],mid+1,r,x);
            else
            findd(T,tr[t][0],l,mid,x);
        }
    }
}

void Change(int t,int l,int r,int x,int s)
{
    int mid=(l+r)/2;
    
    if (l==r) {tr[t][2]+=s;return;}
    
    if (x<=mid)
    Change(tr[t][0],l,mid,x,s);
    else
    Change(tr[t][1],mid+1,r,x,s);
    
    tr[t][2]=min(tr[tr[t][0]][2],tr[tr[t][1]][2]);
}

void pd(int x)
{
    if (t[x]<T)
    {
        t[x]=T;
        
        copy(1);
        rt[x]=len;
    }
}

void clear()
{
    while (tot)
    {
        Change(1,1,n,d[tot][0],d[tot][1]);
        --tot;
    }
}

int main()
{
    freopen("wind.in","r",stdin);
    #ifdef file
    freopen("wind.out","w",stdout);
    #endif
    
    Read(n);Read(m);
    fo(i,1,n)
    Read(c[i]);
    
    mt(1,1,n);
    
    Read(Q);T=1;
    for (;Q;--Q)
    {
        scanf("%s",st);
        
        if (st[0]!='l' && st[0]!='r')
        {
            Read(x),Read(y);
            if (Bz) y=m-y+1;
            
            pd(y);
        }
        
        switch (st[0])
        {
            case 'a':{++tot;d[tot][0]=x;d[tot][1]=1; change(rt[y],1,n,x,y);break;}
            case 'd':{++tot;d[tot][0]=x;d[tot][1]=-1;change(rt[y],1,n,x,0);break;}
            case 'q':{
                switch (st[1])
                {
                    case 'u':{Find=x+1;Find2=0;findu(y,rt[y],1,n,x);printf("%d\n",x-Find+1);break;}
                    case 'd':{Find=x-1;Find2=0;findd(y,rt[y],1,n,x);printf("%d\n",Find-x+1);break;}
                }
                break;
            }
            case 'l':{clear();Bz=0;++T;break;}
            case 'r':{clear();Bz=1;++T;break;}
        }
    }
    
    fclose(stdin);
    fclose(stdout);
    
    return 0;
}

6507. 【GDOI2020模拟03.11】感受清风（wind）