JZOJ 6507 感受清风

发表于 | 分类于 | 13

首先考虑没有 add 操作和 del 操作怎么做。
注意到箱子始终都是推在一边的，故只需要判断第 x 行的箱子个数是否不少于 y 或 m−y+1 便可确定 (x,y) 是否有箱子。
则考虑将维护每一行是否有箱子的线段树按照每一行的箱子个数从大到小可持久化。

现在的问题就在于给定一个全是 0/1 的线段树，如何找到给定位置的前驱 0 或后继 0。
实际上可以通过维护 0 的位置的最值解决，但是由于一些问题此题不可考虑维护最值解决这个问题，于是考虑维护和。
则只需要找到第一个位置使得其到给定位置的和不等于这个位置与给定位置之间的长度即可。
显然可二分，注意找的时候要删去另一边的贡献（前驱则删去给定位置后缀的贡献，后继则删去给定位置前缀的贡献）。

加入修改操作的话，可以先开 m 棵动态开点线段树来维护修改操作，在执行 left 或 right 操作时再合并。
注意到每个修改操作对每一行箱子个数的贡献只有 ±1，故在可持久化线段树上直接修改即可。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <vector>
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x,1);
}
inline void read_s(char *s)
{
    char ch = 0;
    for(;ch < 'a' || ch > 'z';ch = gc());
    for(;ch >= 'a' && ch <= 'z';*s++ = ch,ch = gc());
    *s++ = 0;
}

const int N = 1e6;
int n,m,q,d,a[N + 5];
vector<int> vec[N + 5];
struct s_change
{
    int op,x,y;
} chg[N + 5];
int chg_tot;
struct node
{
    int sum;
    int ls,rs;
} seg[N * 70 + 10];
int rt1[N + 5],rt2[N + 5];
void insert(int x,int k,int &p,int tl,int tr,int per = 0)
{
    static int tot = 0;
    per ? (seg[++tot] = seg[p],p = tot) : (!p && (p = ++tot)),seg[p].sum += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,seg[p].ls,tl,mid,per) : insert(x,k,seg[p].rs,mid + 1,tr,per);
}
int query(int l,int r,int p,int q,int tl,int tr)
{
    if(l > r)
        return 0;
    if((!p && !q) || (l <= tl && tr <= r))
        return seg[p].sum + seg[q].sum;
    int mid = tl + tr >> 1;
    int ret = 0;
    l <= mid && (ret += query(l,r,seg[p].ls,seg[q].ls,tl,mid));
    r > mid && (ret += query(l,r,seg[p].rs,seg[q].rs,mid + 1,tr));
    return ret;
}
int query_l(int x,int s,int p,int q,int tl,int tr)
{
    if(tl == tr)
        return tl;
    int mid = tl + tr >> 1;
    int sum = s + seg[seg[p].rs].sum + seg[seg[q].rs].sum;
    if(mid + 1 > x || sum == x - mid)
        return query_l(x,sum,seg[p].ls,seg[q].ls,tl,mid);
    return query_l(x,s,seg[p].rs,seg[q].rs,mid + 1,tr);
}
int query_r(int x,int s,int p,int q,int tl,int tr)
{
    if(tl == tr)
        return tl;
    int mid = tl + tr >> 1;
    int sum = s + seg[seg[p].ls].sum + seg[seg[q].ls].sum;
    if(mid < x || sum == mid - x + 1)
        return query_r(x,sum,seg[p].rs,seg[q].rs,mid + 1,tr);
    return query_r(x,s,seg[p].ls,seg[q].ls,tl,mid);
}
int main()
{
    freopen("wind.in","r",stdin),freopen("wind.out","w",stdout);
    read(n),read(m);
    for(register int i = 1;i <= n;++i)
        read(a[i]),vec[a[i]].push_back(i);
    for(register int i = m;rt1[i] = rt1[i + 1],i;--i)
        for(register vector<int>::iterator it = vec[i].begin();it != vec[i].end();++it)
            insert(*it,1,rt1[i],1,n,1);
    char op[8];
    int x,y;
    for(read(q);q;--q)
    {
        read_s(op);
        if(op[0] == 'l' || op[0] == 'r')
        {
            d = op[0] == 'r';
            for(register int i = 1;i <= chg_tot;++i)
                chg[i].op ?
                    (insert(chg[i].x,-1,rt2[chg[i].y],1,n),insert(chg[i].x, 1,rt2[++a[chg[i].x]],1,n))
                :
                    (insert(chg[i].x, 1,rt2[chg[i].y],1,n),insert(chg[i].x,-1,rt2[a[chg[i].x]--],1,n));
            chg_tot = 0;
        }
        else
        {
            read(x),read(y),d && (y = m - y + 1);
            if(op[0] == 'a')
                insert(x, 1,rt2[y],1,n),chg[++chg_tot] = (s_change){1,x,y};
            else if(op[0] == 'd')
                insert(x,-1,rt2[y],1,n),chg[++chg_tot] = (s_change){0,x,y};
            else if(op[1] == 'u')
                printf("%d\n",query(1,x,rt1[y],rt2[y],1,n) == x         ? x         : x - query_l(x,-query(x + 1,n,rt1[y],rt2[y],1,n),rt1[y],rt2[y],1,n)    );
            else
                printf("%d\n",query(x,n,rt1[y],rt2[y],1,n) == n - x + 1 ? n - x + 1 :     query_r(x,-query(1,x - 1,rt1[y],rt2[y],1,n),rt1[y],rt2[y],1,n) - x);
        }
    }
}

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!