线段树

题单简介

如何快速求出一个序列的区间和呢？可以使用前缀和。如何快速求出一个序列的最值呢？可 以使用 ST 表。这两种数据结构在建立的时候颇费功夫，但使用的时候效率很高。如果再增加一 个需求：时不时的修改序列的值，那么这两种数据结构就无法高效完成了。不过可以使用线段树 来解决这类问题。

在基础篇中，我们已经学习了二叉树的有关概念。而线段树是一种特殊的二叉树，它可以将 一个线性的序列组织成一个树状的结构，从而可以在对数的时间复杂度下访问序列上的任意一个 区间并进行维护。在本章中，将学习线段树的构建方法和一些简单的应用。

【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 \(k\)。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 \(n, m\)，分别表示该数列数字的个数和操作的总个数。

第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(m\) 行每行包含 \(3\) 或 \(4\) 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 \([x, y]\) 内每个数加上 \(k\)。
  2. 2 x y：输出区间 \([x, y]\) 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

样例输出 #1

1
2
3
11
8
20

提示

对于 \(30\%\) 的数据：\(n \le 8\)，\(m \le 10\)。
对于 \(70\%\) 的数据：\(n \le {10}^3\)，\(m \le {10}^4\)。
对于 \(100\%\) 的数据：\(1 \le n, m \le {10}^5\)。

保证任意时刻数列中所有元素的绝对值之和 \(\le {10}^{18}\)。

【样例解释】

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e6;
#define rep(i,a,n) for(int i=a;i<=n;i++)
ll a[N];
ll w[N*4];
void pushup(const int u)
{
    w[u]=w[u*2]+w[u*2+1];
    //w[u]是区间和，u*2是左子树，u*2+1是右子树
    //节点表示的区间和等于两个子节点所表示的区间之和。
    //有了这个操作，我们就可以递归的求出每一个节点所表示的信息。
}
void build(const int u,int l,int r)
{
    if(l==r)
    //到达叶子节点
    {
        w[u]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    //将区间分成[l,mid]和[mid+1,r]进行递归构造
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    //位运算以便降低时间
    pushup(u);
    //由于子区间的区间和更新当前区间的和
    //你要不断pushup进行更新的意思
}
//单点查询和修改
//我们如果要定位到p这个节点，实际上是需要找到[p,p]
//这个区间，初始时候，左字节点[1,mid]，右边[mid+1,n]
//其中mid=(1+n)>>1
//如果p<=m,就在左子树，向左一路递归就可以
//右子树同理
//如果是修改，就要一路pushup，保证线段树信息的正确性
//就是说一个数字加上某个数时候，就要找到相应的叶子节点
//然后往这个叶子节点的父节点更新区间和，直到根节点为止
//1.单点查询操作
ll query1(int u,int l,int r,int p)
{
//其中u是根节点，l是左边，r是右边，p是要查询的点
if(l==r)
{
    return w[u];
    //到达叶子节点返回值就可以
}
else
{
    int mid=(l+r)/2;
    if(mid>=p)
    //如果查询的位置在左子树
    //就递归查询左子树
{
    return query1(u*2,l,mid,p);
}
else
//反之查询右子树
{
    return query1(u*2+1,mid+1,r,p);
}
}
//由于查询没有对区间和进行修改操作，因此不需要Pushup
}
//2.单点修改操作
ll update1(int u,int l,int r,int p,ll x)
{
    if(l==r)
    {
        w[u]=x;
        //到达叶子节点直接返回即可
    }
    else
    {
        int mid=(l+r)>>1;
        if(mid>=p)
        {
            update1(u*2,l,mid,p,x);
        }
        else
        {
            update1(u*2+1,mid+1,r,p,x);
        }
        pushup(u);
        //更新后要修改当前节点的和
    }
}

//对点的操作到这里就结束了
//下面进入区间查询

//区间查询
//首先假设我们要查询的区间是[l,r]
//如果当前节点代表的区间[L,R]被所询问的区间[l,r]所包含
//l,r就是 查询的区间
//那么直接返回当前区间的区间和
//也即是说L>=r并且R<=r就被包含了就直接包含
//如果两个区间没有交集，直接返回0
//如果没有被包含且两区间有交，则递归左右子节点处理即可
//所以无论我们查询多大的区间，都可以拆成一些（不超过logn）预处理过的子区间，把这些子区间的区间和加起来，就是答案。

//判断[l,r]是否能够完全包含，是的话就直接返回这一块的值
bool inrange(int L,int R,int l,int r)
{
    return (l<=L)&&(R<=r);
    //判断是否包含
}
//跟刚才那个是极端，这个就是毫无交集了
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
    //判断两者的交集是否无解
}
//区间修改
ll lzy[N*4];
//重中之重的部分就是这一块，所谓的区间修改和区间修改相应的查询，都会变化
void maketag(int u,int len,ll x)
{
    lzy[u]+=x;
    //给这个点加上懒标记
    w[u]+=len*x;
    //这个点加上相应的值
}
//懒标记的下放
//肯定要分区间节点，左子树和右子树的下放
//注意要加上长度
void pushdown(int u,int L,int R)
{
    int Mid=(L+R)/2;
    maketag(u*2,Mid-L+1,lzy[u]);
    maketag(u*2+1,R-Mid,lzy[u]);
    lzy[u]=0;
    //tag的下放所以避免重复修改，当前层要清空标记
}
ll query(int u,int L,int R,int l,int r)
{
    if(inrange(L,R,l,r))
    {
        return w[u];
    }
    //和上面一样如果一样就进行包含求和
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        //求平均操作
        pushdown(u,L,R);
        //下放操作
        return query(u*2,L,Mid,l,r)+query(u*2+1,Mid+1,R,l,r);
        //直接分左右查询
    }
    else
    {
        return 0;
    }
}
void update(int u,int L,int R,int l,int r,ll x)
{
    if(inrange(L,R,l,r))
    {
        maketag(u,R-L+1,x);
        //直接打上节点
    }
    //包含就直接下放
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        pushdown(u,L,R);
        //进行下放，然后进行更新
        update(u*2,L,Mid,l,r,x);
        update(u*2+1,Mid+1,R,l,r,x);
    pushup(u);
    }
}
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    cin>>a[i];
}
build(1,1,n);
rep(i,1,m)
{
    int op,x,y;
    cin>>op;
    ll k;
    if(op==1)
    {
        cin>>x>>y>>k;
        update(1,1,n,x,y,k);
    }
    else
    {
        cin>>x>>y;
        cout<<(query(1,1,n,x,y))<<'\n';
    }
}
}
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
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{
    int sum;
    int l,r;
    int add;//懒标记
}tr[N*4];//线段树要开四倍空间哦
int a[N];//原数列
inline void pushup(int x){
    tr[x].sum=tr[2*x].sum+tr[2*x+1].sum;//pushup操作
}
inline void pushudown(int x){
    if(tr[x].add){
        //如果这个节点上有懒标记
        tr[2*x].add+=tr[x].add,tr[2*x+1].add+=tr[x].add;
        //把这个节点的懒标记给他的两个子节点
        tr[2*x].sum+=tr[x].add*(tr[2*x].r-tr[2*x].l+1);
        tr[2*x+1].sum+=tr[x].add*(tr[2*x+1].r-tr[2*x+1].l+1);
        //分别给它的两个子节点修改
        tr[x].add=0;
        //别忘了清空这个节点的懒标记
    }
}
void build(int x,int l,int r){
    //建树操作
    tr[x].l=l,tr[x].r=r,tr[x].add=0;
    if(l==r){
        tr[x].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*x,l,mid),build(2*x+1,mid+1,r);
    pushup(x);
}
int query(int x,int l,int r){
    if(l<=tr[x].l&&r>=tr[x].r) return tr[x].sum;
    pushudown(x);//注意，区间查询时也要下懒传标记
    int mid=(tr[x].l+tr[x].r)/2,sum=0;
    if(l<=mid) sum+=query(x*2,l,r);
    if(r>mid) sum+=query(x*2+1,l,r);
    return sum; 
}
void update(int now,int l,int r,int k){
    if(l<=tr[now].l&&r>=tr[now].r){
        //如果查到子区间了
        tr[now].sum+=k*(tr[now].r-tr[now].l+1);//先修改这个区间
        tr[now].add+=k;//然后给它打上懒标记
        //注：这里一定要分清顺序，先修改，再标记！
    }
    else{
        //如果需要继续向下查询
        pushudown(now);//先把懒标记向下传
        int mid=(tr[now].l+tr[now].r)/2;
        //这里很像区间查询
        if(l<=mid) update(now*2,l,r,k);
        if(r>mid) update(now*2+1,l,r,k);
        pushup(now);//最后别忘了pushup一下
    }
}
int n,q;
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(q--){
        int l,r,k,c;
        cin>>c>>l>>r;
        if(c==1){
            cin>>k;
            update(1,l,r,k);
        }
        else cout<<query(1,l,r)<<endl;
    }
    return 0;
}

[TJOI2009] 开关

题目描述

现有 \(n\) 盏灯排成一排，从左到右依次编号为：\(1\)，\(2\)，……，\(n\)。然后依次执行 \(m\) 项操作。

操作分为两种：

  1. 指定一个区间 \([a,b]\)，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开）；
  2. 指定一个区间 \([a,b]\)，要求你输出这个区间内有多少盏灯是打开的。

灯在初始时都是关着的。

输入格式

第一行有两个整数 \(n\) 和 \(m\)，分别表示灯的数目和操作的数目。

接下来有 \(m\) 行，每行有三个整数，依次为：\(c\)、\(a\)、\(b\)。其中 \(c\) 表示操作的种类。

  • 当 \(c\) 的值为 \(0\) 时，表示是第一种操作。
  • 当 \(c\) 的值为 \(1\) 时，表示是第二种操作。

\(a\) 和 \(b\) 则分别表示了操作区间的左右边界。

输出格式

每当遇到第二种操作时，输出一行，包含一个整数，表示此时在查询的区间中打开的灯的数目。

样例 #1

样例输入 #1

1
2
3
4
5
6
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

样例输出 #1

1
2
1
2

提示

数据规模与约定

对于全部的测试点，保证 \(2\le n\le 10^5\)，\(1\le m\le 10^5\)，\(1\le a,b\le n\)，\(c\in\{0,1\}\)。

本题要点是懒标记，由于状态只有0，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
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e6;
#define rep(i,a,n) for(int i=a;i<=n;i++)
ll a[N];
ll w[N*4];
void pushup(const int u)
{
    w[u]=w[u*2]+w[u*2+1];
    //w[u]是区间和，u*2是左子树，u*2+1是右子树
}
void build(const int u,int l,int r)
{
    if(l==r)
    //到达叶子节点
    {
        w[u]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    //将区间分成[l,mid]和[mid+1,r]进行递归构造
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    //位运算以便降低时间
    pushup(u);
    //由于子区间的区间和更新当前区间的和
}
//区间查询
//首先假设我们要查询的区间是[l,r]
//如果当前节点代表的区间[L,R]被所询问的区间[l,r]所包含
//那么直接返回当前区间的区间和
//也即是说L>=r并且R<=r就被包含了就直接包含
//如果两个区间没有交集，直接返回0
//如果没有被包含且两区间有交，则递归左右子节点处理即可
bool inrange(int L,int R,int l,int r)
{
    return (l<=L)&&(R<=r);
    //判断是否包含
}
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
    //判断两者的交集是否无解
}
//区间修改
ll lzy[N*4];
void maketag(int u,int len,ll x)
{

    w[u] = len - w[u];
    //计算总和
    lzy[u] ^=1;
    //异或一下
}
void pushdown(int u,int L,int R)
{
    int Mid=(L+R)/2;
    maketag(u*2,Mid-L+1,lzy[u]);
    maketag(u*2+1,R-Mid,lzy[u]);
    lzy[u]=0;
    //tag的下放所以避免重复修改，当前层要清空标记
}
ll query(int u,int L,int R,int l,int r)
{
    if(inrange(L,R,l,r))
    {
        return w[u];
    }
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        if(lzy[u]==1)
        {
            pushdown(u, L, R);
        }
        return query(u*2,L,Mid,l,r)+query(u*2+1,Mid+1,R,l,r);   
    }
    else
    {
        return 0;
    }
}
void update(int u,int L,int R,int l,int r,ll x)
{
    if(inrange(L,R,l,r))
    {
        maketag(u,R-L+1,x);
    }
    else if(!outrange(L,R,l,r))
    {
        int Mid=(L+R)/2;
        if(lzy[u]==1)
        {
            pushdown(u,L,R);
        }
        update(u*2,L,Mid,l,r,x);
        update(u*2+1,Mid+1,R,l,r,x);
        pushup(u);
    }
}
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    a[i]=0;
}
build(1,1,n);
rep(i,1,m)
{
    int op,x,y;
    cin>>op;
    ll k;
    if(op==0)
    {
        cin>>x>>y;;
        update(1,1,n,x,y,1);
    }
    else
    {
        cin>>x>>y;
    cout<<query(1,1,n,x,y)<<'\n';
    }
}
}

无聊的数列

题目背景

无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）

题目描述

维护一个数列 \(a_i\)，支持两种操作：

  • 1 l r K D：给出一个长度等于 \(r-l+1\) 的等差数列，首项为 \(K\)，公差为 \(D\)，并将它对应加到 \([l,r]\) 范围中的每一个数上。即：令 \(a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D\)。

  • 2 p：询问序列的第 \(p\) 个数的值 \(a_p\)。

输入格式

第一行两个整数数 \(n,m\) 表示数列长度和操作个数。

第二行 \(n\) 个整数，第 \(i\) 个数表示 \(a_i\)。

接下来的 \(m\) 行，每行先输入一个整数 \(opt\)。

若 \(opt=1\) 则再输入四个整数 \(l\ r\ K\ D\)；

若 \(opt=2\) 则再输入一个整数 \(p\)。

输出格式

对于每个询问，一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5 2
1 2 3 4 5
1 2 4 1 2
2 3

样例输出 #1

1
6

提示

数据规模与约定

对于 \(100\%\) 数据，\(0\le n,m \le 10^5,-200\le a_i,K,D\le 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n\)。

本题需要两个懒标记

一个记录首项

一个记录公差

期间有一些需要注意的事项

那些参数的传递有点细节，需要注意，调了半个月（）

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
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6;
#define rep(i, a, n) for (ll i = a; i <= n; i++)
ll a[N];
ll w[N * 4];
void pushup(const ll u)
{
    w[u] = w[u * 2] + w[u * 2 + 1];
    // w[u]是区间和，u*2是左子树，u*2+1是右子树
}
void build(const int u, int l, int r)
{
    if (l == r)
    // 到达叶子节点
    {
        w[u] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    // 将区间分成[l,mid]和[mid+1,r]进行递归构造
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    // 位运算以便降低时间
    pushup(u);
    // 由于子区间的区间和更新当前区间的和
}
ll first[N * 4]; // 存放首
ll cha[N * 4];   // 存放公差
bool inrange(ll L, ll R, ll l, ll r)
{
    return (l <= L) && (R <= r);
    // 判断是否包含
}
bool outrange(ll L, ll R, ll l, ll r)
{
    return (L > r) || (R < l);
    // 判断两者的交集是否无解
}
// 区间修改
void maketag(ll u, ll len, ll x, ll y)
// 一个是首项，一个是公差，一个是长度
{
    ll mid = x + y * (len - 1ll);
    first[u] += x;
    cha[u] += y;
    w[u] += 1ll * (mid + x) * len / 2;
    //根节点要加上求和
}
void pushdown(ll u, ll L, ll R)
{
    ll Mid = (L + R) / 2;
    maketag(u * 2, Mid - L + 1, first[u], cha[u]);
    maketag(u * 2 + 1, R - Mid, first[u] + (Mid - L + 1) * cha[u], cha[u]);
    //注意区间下放的首项目
    cha[u] = 0;
    //差置为0
    first[u] = 0;
    //首项置为0
    // tag的下放所以避免重复修改，当前层要清空标记
}
ll query(ll u, ll L, ll R, ll l, ll r)
{
    if (inrange(L, R, l, r))
    {
        return w[u];
    }
    else if (!outrange(L, R, l, r))
    {
        ll Mid = (L + R) >> 1;
        pushdown(u, L, R);
        return query(u * 2, L, Mid, l, r) + query(u * 2 + 1, Mid + 1, R, l, r);
    }
    else
    {
        return 0;
    }
}
void update(ll u, ll L, ll R, ll l, ll r, ll x, ll y)
// 后面一个是首项，一个是公差
{
    if (inrange(L, R, l, r))
    {
        maketag(u, R - L + 1, x, y);
    }
    else if (!outrange(L, R, l, r))
    {
        ll Mid = (L + R) / 2;
        pushdown(u, L, R);
        update(u * 2, L, Mid, l, r, x, y);
        update(u * 2 + 1, Mid + 1, R, l, r, x + (Mid - L +1) * y, y);
        //这里就是这个区间的首项目
        //注意是Mid-L+1
        pushup(u);
    }
}
int main()
{
    ll n, m;
    cin >> n >> m;
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    rep(i, 1, m)
    {
        ll op, x, y;
        cin >> op;
        ll k;
        if (op == 1)
        {
            ll x, y;
            ll z, k;
            cin >> x >> y >> z >> k;
            update(1, 1, n, x, y, (1-x)*k+z, k);
            //我们要传递的是在a[1]这个地方的首项，这样后面就不会出错
            //就是我们知道x这个地方的首项，去求1时候的首项
        }
        else
        {
            ll x;
            cin >> x;
            cout << query(1, 1, n, x, x) << '\n';
        }
    }
}

扶苏的问题

题目描述

给定一个长度为 \(n\) 的序列 \(a\)，要求支持如下三个操作：

  1. 给定区间 \([l, r]\)，将区间内每个数都修改为 \(x\)。
  2. 给定区间 \([l, r]\)，将区间内每个数都加上 \(x\)。
  3. 给定区间 \([l, r]\)，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度 \(n\) 和操作的个数 \(q\)。
第二行有 \(n\) 个整数，第 \(i\) 个整数表示序列中的第 \(i\) 个数 \(a_i\)。
接下来 \(q\) 行，每行表示一个操作。每行首先有一个整数 \(op\)，表示操作的类型。

  • 若 \(op = 1\)，则接下来有三个整数 \(l, r, x\)，表示将区间 \([l, r]\) 内的每个数都修改为 \(x\)。
  • 若 \(op = 2\)，则接下来有三个整数 \(l, r, x\)，表示将区间 \([l, r]\) 内的每个数都加上 \(x\)。
  • 若 \(op = 3\)，则接下来有两个整数 \(l, r\)，表示查询区间 \([l, r]\) 内的最大值。

输出格式

对于每个 \(op = 3\) 的操作，输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

样例输出 #1

1
2
3
7
6
-1

样例 #2

样例输入 #2

1
2
3
4
5
6
4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

样例输出 #2

1
0

提示

数据规模与约定

  • 对于 \(10\%\) 的数据，\(n = q = 1\)。
  • 对于 \(40\%\) 的数据，\(n, q \leq 10^3\)。
  • 对于 \(50\%\) 的数据，\(0 \leq a_i, x \leq 10^4\)。
  • 对于 \(60\%\) 的数据，\(op \neq 1\)。
  • 对于 \(90\%\) 的数据，\(n, q \leq 10^5\)。
  • 对于 \(100\%\) 的数据，\(1 \leq n, q \leq 10^6\)，\(1 \leq l, r \leq n\)，\(op \in \{1, 2, 3\}\)，\(|a_i|, |x| \leq 10^9\)。

提示

请注意大量数据读入对程序效率造成的影响。

其实还是懒标记的问题，只需要修改懒标记就行了

弄一个设置值的懒标记

和一个加的懒标记

设置值的初始化为正无穷

设置的加的懒标记为0

确认一下优先级

优先级肯定是设置值的高，因为一但设置，之前怎么加都是没用的

当我们要设置值的时候，set就设置为那个值，add清零

如果要加，康康设置有没有设置过（inf),如果没有，就可以添加到add，如果有，就添加到set那里

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6+10;
ll inf = 1145141919810;
ll lzy_add[N * 4];
ll lzy_set[N * 4];
int n,m;
#define rep(i, a, n) for (int i = a; i <= n; i++)
ll a[N];
ll w[N * 4];
void pushup(const int u)
{
    w[u] = max(w[u <<1], w[u<<1|1]);
    // w[u]是区间和，u*2是左子树，u*2+1是右子树
}
void build(const int u, int l, int r)
{
    lzy_set[u] = inf;
    //这里是初始化
    if (l == r)
    // 到达叶子节点
    {
        w[u] = a[l];
        return;
    }
    int mid = (l + r)  /2;
    // 将区间分成[l,mid]和[mid+1,r]进行递归构造
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    // 位运算以便降低时间
    pushup(u);
    // 由于子区间的区间和更新当前区间的和
}
// 区间查询
// 首先假设我们要查询的区间是[l,r]
// 如果当前节点代表的区间[L,R]被所询问的区间[l,r]所包含
// 那么直接返回当前区间的区间和
// 也即是说L>=r并且R<=r就被包含了就直接包含
// 如果两个区间没有交集，直接返回0
// 如果没有被包含且两区间有交，则递归左右子节点处理即可

bool inrange(int L, int R, int l, int r)
{
    return (l <= L) && (R <= r);
    // 判断是否包含
}
bool outrange(int L, int R, int l, int r)
{
    return (L > r) || (R < l);
    // 判断两者的交集是否无解
}
//以上都是模板
// 区间修改
void maketag(int u, ll x, int type)
{
    if (type == 1)
        //1就是直接修改
    {
        lzy_add[u] = 0;
        lzy_set[u] = x;
        w[u] = x;
    }
    else
        //2就是加上
    {
         w[u] += x;
        if (lzy_set[u] != inf)
        {
            lzy_set[u] += x;
        }
        //就给设置加上，因为这时候真正的值在set那里
        else
        {
            lzy_add[u] += x;
            //不然就没有set操作，只需要add加x就行
        }
    }
}
void pushdown(int u)
{
    if (lzy_set[u] != inf)
    {
        maketag(u * 2, lzy_set[u], 1);
        maketag(u * 2 + 1, lzy_set[u], 1);
        lzy_set[u] = inf;
    }
    else
    {
        maketag(u * 2, lzy_add[u], 2);
        maketag(u * 2 + 1, lzy_add[u], 2);
        lzy_add[u] = 0;
    }
    // tag的下放所以避免重复修改，当前层要清空标记
}
ll query(int u, int L, int R, int l, int r)
{
    if (inrange(L, R, l, r))
    {
        return w[u];
    }
    else if (!outrange(L, R, l, r))
    {
        int Mid = (L + R) / 2;
            pushdown(u);
        return max(query(u * 2, L, Mid, l, r), query(u * 2 + 1, Mid + 1, R, l, r));
    }
    else
    {
        return -inf;
        //这里不能是0，必须是-无穷不然会错（别问我怎么知道）
    }
}
//加个type
void update(int u, int L, int R, int l, int r, ll x, int type)
{
    if (inrange(L, R, l, r))
    {
        maketag(u, x, type);
    }
    else if (!outrange(L, R, l, r))
    {
        int Mid = (L + R) / 2;
        pushdown(u);
        update(u * 2, L, Mid, l, r, x, type);
        update(u * 2 + 1, Mid + 1, R, l, r, x, type);
        pushup(u);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin >> n >> m;
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    rep(i, 1, m)
    {
        int op, x, y;
        cin >> op;
        ll k;
        if (op == 1)
        {
            cin >> x >> y >> k;
            update(1, 1, n, x, y, k, 1);
        }
        else if (op == 2)
        {
            cin >> x >> y >> k;
            update(1, 1, n, x, y, k, 2);
        }
        else
        {
            cin >> x >> y;
            cout << query(1, 1, n, x, y) << '\n';
        }
    }
}

【模板】线段树 2

题目描述

如题，已知一个数列，你需要进行下面三种操作：

  • 将某区间每一个数乘上 \(x\)；
  • 将某区间每一个数加上 \(x\)；
  • 求出某区间每一个数的和。

输入格式

第一行包含三个整数 \(n,q,m\)，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 \(n\) 个用空格分隔的整数，其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(q\) 行每行包含若干个整数，表示一个操作，具体如下：

操作 \(1\)： 格式：1 x y k 含义：将区间 \([x,y]\) 内每个数乘上 \(k\)

操作 \(2\)： 格式：2 x y k 含义：将区间 \([x,y]\) 内每个数加上 \(k\)

操作 \(3\)： 格式：3 x y 含义：输出区间 \([x,y]\) 内每个数的和对 \(m\) 取模所得的结果

输出格式

输出包含若干行整数，即为所有操作 \(3\) 的结果。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

样例输出 #1

1
2
17
2

提示

【数据范围】

对于 \(30\%\) 的数据：\(n \le 8\)，\(q \le 10\)。
对于 \(70\%\) 的数据：$n ^3 \(，\)q ^4$。
对于 \(100\%\) 的数据：\(1 \le n \le 10^5\)，\(1 \le q \le 10^5\)。

除样例外，\(m = 571373\)。

（数据已经过加强 _）

样例说明：

故输出应为 \(17\)、\(2\)（\(40 \bmod 38 = 2\)）。 好的，我帮你排版清晰一些，内容如下：

问题核心：懒标记如何处理

很明显，乘法和加法操作都会涉及懒标记。我们需要安排懒标记的 pushdown 顺序。

假设两个懒标记分别为 mul（乘法）和 add（加法），根据顺序：

  1. 基础公式：
    数值更新为：
    $ + $

  2. 加入新的 add 懒标记时：
    新数值变为：
    $ + + $

  3. 加入新的 mul 懒标记时：
    新数值变为：
    $ + $

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using  namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
//本题需要乘法标记和加法标记
//主要是顺序
using ll=long long;
const int N=1e6+10;
int p;
ll a[N];
ll w[N<<2];
ll lzy_add[N<<2];
ll lzy_mul[N<<2];
void pushup(const int u)
{
    //w[u]是区间和
    w[u]=(w[u<<1]+w[u<<1|1])%p;
}
void build(const int u,int l,int r)
{
    lzy_mul[u]=1;
    //一样进行初始化
    if(l==r)
    {
        w[u]=a[l];
        return ;
    }
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
bool Inrange(int L,int R,int l,int r)
{
    return (l<=L&&r>=R);
}
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
}
//上面操作都没什么，主要还下面

void maketag(int u,int L,int R,ll x ,int type)
{
    if(type==1)
    {
        (lzy_add[u]*=x)%=p;
        (lzy_mul[u]*=x)%=p;
        (w[u]*=x)%=p;
        //三连击
    }
    else
    {
        (lzy_add[u]+=x)%=p;
        (w[u]+=(R-L+1)*x)%=p;
        //二连击
    }    
}
void pushdown(int u,int L,int R)
{
int Mid=(L+R)/2;
maketag(u<<1,L,Mid,lzy_mul[u],1);
maketag(u << 1, L, Mid, lzy_add[u], 2);
maketag(u << 1|1,  Mid+1,R, lzy_mul[u], 1);
maketag(u<<1|1,Mid+1,R,lzy_add[u],2);
lzy_mul[u]=1;
    //下放清空
lzy_add[u]=0;
    //加法清空
}
ll query(int u, int L, int R, int l, int r)
{
    if (Inrange(L, R, l, r))
    {
        return w[u]%p;
    }
    else if (!outrange(L, R, l, r)) 
    {
        int Mid = (L + R) / 2;
        pushdown(u, L, R);
        return (((query(u * 2, L, Mid, l, r))%p) + ((query(u * 2 + 1, Mid + 1, R, l, r))%p))%p;
    }
    else
    {
        return 0;
    }
}
void update(int u, int L, int R, int l, int r, ll x,int type)
{
    if (Inrange(L, R, l, r))
    {
        maketag(u, L,R, x,type);
    }
    else if (!outrange(L, R, l, r))
    {
        int Mid = (L + R) / 2;
        pushdown(u, L, R);
        update(u <<1, L, Mid, l, r, x,type);
        update(u<<1|1, Mid + 1, R, l, r, x,type);
        pushup(u);
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n, m;
    cin >> n >> m>>p;
    rep(i, 1, n)
    {
        cin >> a[i];
}
build(1,1,n);
int opt;
rep(i,1,m)
{
cin>>opt;
    //乘法
if(opt==1)
{
    int x,y;
    ll z;
    cin>>x>>y>>z;
    update(1,1,n,x,y,z,1);
}
    //加法
else if(opt==2)
{
    int x, y;
    ll z;

    cin >> x >> y >> z;
    update(1, 1, n, x, y, z, 2);
}
    //求和
else
{
    int x,y;
    cin>>x>>y;
    cout<<query(1,1,n,x,y)%p<<'\n';

}

}


}

小白逛公园

题目背景

小新经常陪小白去公园玩，也就是所谓的遛狗啦…

题目描述

在小新家附近有一条“公园路”，路的一边从南到北依次排着 \(n\) 个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。

一开始，小白就根据公园的风景给每个公园打了分。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第 \(a\) 个和第 \(b\) 个公园之间（包括 \(a, b\) 两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧。

输入格式

第一行，两个整数 \(n\) 和 \(m\)，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。

接下来 \(n\) 行，每行一个整数，依次给出小白开始时对公园的打分。

接下来 \(m\) 行，每行三个整数。其中第一个整数 \(k\) 为 \(1\) 或 \(2\)。

  • \(k=1\) 表示，小新要带小白出去玩，接下来的两个整数 \(a\) 和 \(b\) 给出了选择公园的范围 \((1 \le a,b \le n)\)。测试数据可能会出现 \(a > b\) 的情况，需要进行交换；
  • \(k=2\) 表示，小白改变了对某个公园的打分，接下来的两个整数 \(p\) 和 \(s\)，表示小白对第 \(p\) 个公园的打分变成了 \(s(1\le p\le N)\)。

输出格式

小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
5 3
1
2
-3
4
5
1 2 3
2 2 -1
1 2 3

样例输出 #1

1
2
2
-1

提示

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n \le 5 \times 10^5\)，\(1 \le m \le 10^5\)，所有打分都是绝对值不超过 \(1000\) 的整数。

本题貌似不需要懒标记（）

maxleft，以左端点为头的 和最大的连续序列。

maxright，以右端点为尾的 和最大的连续序列。

sum，这段序列的总和

ans，这段序列中的最大的连续序列

sum[k]=sum[k∗2]+sum[k∗2+1];

tree[k].maxleft=max(tree[k2].maxleft,tree[k2].sum+tree[k2+1].maxleft);//更新maxleft

tree[k].maxright=max(tree[k2+1].maxright,tree[k2].maxright+tree[k2+1].sum);//更新maxright

​ tree[k].ans=max(max(tree[k2].ans,tree[k2+1].ans),tree[k2].maxright+tree[k2+1].maxleft);//更新ans

这样就结束了

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
#include<iostream>
#include<cstdio>
#define N 2000001
using namespace std;
int n, m;
struct Tree
{
	int l, r;
	long long maxleft, maxright, sum,ans;
}tree[N];
void pushup(int k)
{
	tree[k].sum = tree[k * 2].sum + tree[k * 2 + 1].sum;
	tree[k].maxleft = max(tree[k * 2].maxleft, tree[k * 2].sum + tree[k * 2 + 1].maxleft);
	tree[k].maxright = max(tree[k * 2 + 1].maxright, tree[k * 2].maxright + tree[k * 2 + 1].sum);
	tree[k].ans = max(max(tree[k * 2].ans, tree[k * 2 + 1].ans), tree[k * 2].maxright + tree[k * 2 + 1].maxleft);
}
void build(int l, int r, int u)
{
	tree[u].l = l;
	tree[u].r = r;
	if (l == r)
	{
		cin >> tree[u].sum;
		tree[u].maxleft = tree[u].maxright = tree[u].ans = tree[u].sum;
		return;
	}
	int mid = (l + r)/2;
	build( l, mid,u*2);
	build( mid + 1, r,u*2+1);
	pushup(u);
}
Tree query(int u, int l, int r)
{
	if (l <= tree[u].l && tree[u].r <= r)
	{
		return tree[u];
	}
	int mid =(tree[u].l + tree[u].r)/2;
	if (r <= mid)
	{
		return query(u * 2,l, r);
	}
	else
	{
		if (l > mid)
		{
		return 	query(u * 2 + 1, l, r);
		}
		else
		{
			Tree t, a = query(u * 2, l, r), b = query(u * 2 + 1, l, r);
			t.maxleft = max(a.maxleft, a.sum + b.maxleft);//做类似的合并区间
			t.maxright = max(b.maxright, a.maxright + b.sum);
			t.ans = max(max(a.ans, b.ans), a.maxright + b.maxleft);
			return t;
		}
	}
}
void update(int u, int x, int y)
{
	if (tree[u].l == tree[u].r)
	{
		tree[u].maxleft = tree[u].maxright = tree[u].ans = tree[u].sum = y;
		return;
	}
	int mid = (tree[u].l + tree[u].r) / 2;
	if (x <= mid)
	{
		update(u * 2, x, y);
	}
	else update(u * 2 + 1, x, y);
	pushup(u);
}
int main()
{
	cin >> n;
	cin >> m;
	build(1, n, 1);
	while (m--)
	{
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1)
		{
			if (x > y)
			{
				swap(x, y);
			}
			Tree t = query(1, x, y);
			cout << t.ans << '\n';
		}
		else
		{
			update(1, x, y);
		}
	}
	return 0;
}

GSS3 - Can you answer these queries III

题面翻译

\(n\) 个数，\(q\) 次操作

操作0 x y把\(A_x\) 修改为\(y\)

操作1 l r询问区间\([l, r]\) 的最大子段和

感谢 @Edgration 提供的翻译

题目描述

You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

输入格式

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

输出格式

For each query, print an integer as the problem required.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

样例输出 #1

1
2
3
6
4
-3

双倍经验啊！！！

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
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 2000001;
int n, m;
struct Tree
{
	int l, r;
	long long maxleft, maxright, sum,ans;
}tree[N];
void pushup(int u)
{
	tree[u].sum = tree[u*2].sum + tree[u *2+1].sum;
	tree[u].maxleft = max(tree[u*2].maxleft, tree[u *2].sum + tree[u*2+1].maxleft);
	tree[u].maxright = max(tree[u*2+1].maxright, tree[u *2].maxright + tree[u *2+1].sum);
	tree[u].ans = max(max(tree[u*2].ans, tree[u*2+1].ans), tree[u*2].maxright + tree[u*2+1].maxleft);
}
void build(int l, int r, int u)
{
	tree[u].l = l;
	tree[u].r = r;
	if (l == r)
	{
		cin >> tree[u].sum;
		tree[u].maxleft = tree[u].maxright = tree[u].ans = tree[u].sum;
		return;
	}
	int mid = (l + r)/2;
	build( l, mid,2*u);
	build( mid + 1, r,2*u+1);
	pushup(u);
}
Tree query(int u, int l, int r)
{
	if (l <= tree[u].l && tree[u].r <= r)
	{
		return tree[u];
	}
	int mid =(tree[u].l + tree[u].r)/2;
	if (r <= mid)
	{
	return 	query(u * 2,l, r);
	}
	else
	{
		if (l > mid)
		{
		return 	query(u * 2 + 1, l, r);
		}
		else
		{
			Tree t, a = query(u * 2, l, r), b = query(u * 2 + 1, l, r);
			t.maxleft = max(a.maxleft, a.sum + b.maxleft);//做类似的合并区间
			t.maxright = max(b.maxright, a.maxright + b.sum);
			t.ans = max(max(a.ans, b.ans), a.maxright + b.maxleft);
			return t;
		}
	}
}
void update(int u, int x, int y)
{
	if (tree[u].l == tree[u].r)
	{
		tree[u].maxleft = tree[u].maxright = tree[u].ans = tree[u].sum = y;
		return;
	}
	int mid = (tree[u].l + tree[u].r) / 2;
	if (x <= mid)
	{
		update(u * 2, x, y);
	}
	else update(u * 2 + 1, x, y);
	pushup(u);
}
int main()
{
	cin >> n;
	build(1, n, 1);
	cin >> m;
	while (m--)
	{
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1)
		{
			if (x > y)
			{
				swap(x, y);
			}
			Tree t = query(1, x, y);
			cout << t.ans << '\n';
		}
		else
		{
			update(1, x, y);
		}
	}
	return 0;
}

逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 \(a_i>a_j\) 且 \(i<j\) 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 \(n\)，表示序列中有 \(n\)个数。

第二行 \(n\) 个数，表示给定的序列。序列中每个数字不超过 \(10^9\)。

输出格式

输出序列中逆序对的数目。

样例 #1

样例输入 #1

1
2
6
5 4 2 6 3 1

样例输出 #1

1
11

提示

对于 \(25\%\) 的数据，\(n \leq 2500\)

对于 \(50\%\) 的数据，\(n \leq 4 \times 10^4\)。

对于所有数据，\(n \leq 5 \times 10^5\)

请使用较快的输入输出

应该不会 \(O(n^2)\) 过 50 万吧 by chen_zhe

归并排序，详见分治与倍增

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
// P1908 逆序对
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
const int N = 1e6;
int n, a[N],t[N];
ll ans;
void merge_sort(int a[],int l,int r)
{
    if(l==r)
{
    return ;
}
int mid=l+r>>1;
merge_sort(a,l,mid),merge_sort(a,mid+1,r);
for(int i=l,j=l,k=mid+1;i<=r;i++)
{
    if(j==mid+1)
    {
        t[i]=a[k++];
    }
    else if(k==r+1)
    {
        t[i]=a[j++];
        ans+=k-mid-1;
    }
    else if(a[j]<=a[k])
    {
        t[i]=a[j++];
         ans+=k-mid-1;
    }
    else
    {
        t[i]=a[k++];
    }
}
for (int i = l; i <= r; i++)
{
    a[i] = t[i];
}
}
int main()
{
    cin>>n;
    rep(i,1,n)
    {
        cin>>a[i];
    }
    merge_sort(a,1,n);
    cout<<ans;
    return 0;
}

忠诚

题目描述

老管家是一个聪明能干的人。他为财主工作了整整 \(10\) 年。财主为了让自已账目更加清楚，要求管家每天记 \(k\) 次账。由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按 \(1, 2, 3 \ldots\) 编号，然后不定时的问管家问题，问题是这样的：在 \(a\) 到 \(b\) 号账中最少的一笔是多少？为了让管家没时间作假，他总是一次问多个问题。

输入格式

输入中第一行有两个数 \(m, n\)，表示有 \(m\) 笔账 \(n\) 表示有 \(n\) 个问题。

第二行为 \(m\) 个数，分别是账目的钱数。

后面 \(n\) 行分别是 \(n\) 个问题，每行有 \(2\) 个数字说明开始结束的账目编号。

输出格式

在一行中输出每个问题的答案，以一个空格分割。

样例 #1

样例输入 #1

1
2
3
4
5
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10

样例输出 #1

1
2 3 1

提示

对于 \(100\%\) 的数据，\(m \leq 10^5\)，\(n \leq 10^5\)。

ST表裸题

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
using ll=long long;
int st[N][20];
int lg[N];
int n,m;
int main()
{
    ios::sync_with_stdio(0);
 	cin.tie(0);
 	cout.tie(0);
    cin>>n>>m;
    lg[1]=0;
    for(int i=2;i<=n;i++)
    {
        lg[i]=lg[i>>1]+1;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>st[i][0];
    }
    for(int j=1;j<=lg[n];j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
    int l,r;
    while(m--)
    {
        cin>>l>>r;
        int t=lg[r-l+1];
        cout<<min(st[l][t],st[r-(1<<t)+1][t])<<' ';
    }  
}

方差

题目背景

滚粗了的 HansBug 在收拾旧数学书，然而他发现了什么奇妙的东西。

题目描述

蒟蒻 HansBug 在一本数学书里面发现了一个神奇的数列，包含 \(N\) 个实数。他想算算这个数列的平均数和方差。

输入格式

第一行包含两个正整数 \(N,M\)，分别表示数列中实数的个数和操作的个数。

第二行包含 \(N\) 个实数，其中第 \(i\) 个实数表示数列的第 \(i\) 项。

接下来 \(M\) 行，每行为一条操作，格式为以下三种之一：

操作 \(1\)：1 x y k ，表示将第 \(x\) 到第 \(y\) 项每项加上 \(k\)，\(k\) 为一实数。
操作 \(2\)：2 x y ，表示求出第 \(x\) 到第 \(y\) 项这一子数列的平均数。
操作 \(3\)：3 x y ，表示求出第 \(x\) 到第 \(y\) 项这一子数列的方差。

输出格式

输出包含若干行，每行为一个实数，即依次为每一次操作 \(2\) 或操作 \(3\) 所得的结果（所有结果四舍五入保留 \(4\) 位小数）。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 1 4
3 1 5
1 1 1 1
1 2 2 -1
3 1 5

样例输出 #1

1
2
3
3.0000
2.0000
0.8000

提示

关于方差：对于一个有 \(n\) 项的数列 \(A\)，其方差 \(s^2\) 定义如下： \[s^2=\frac{1}{n}\sum\limits_{i=1}^n\left(A_i-\overline A\right)^2\] 其中 \(\overline A\) 表示数列 \(A\) 的平均数，\(A_i\) 表示数列 \(A\) 的第 \(i\) 项。

样例说明：

操作步骤 输入内容 操作要求 数列 输出结果 说明
\(0\) - - 1 5 4 2 3 - -
\(1\) 2 1 4 求 \(\left[1,4\right]\) 内所有数字的平均数 1 5 4 2 3 3.0000 平均数 \(=\left(1+5+4+2\right)\div 4=3.0000\)
\(2\) 3 1 5 求 \(\left[1,5\right]\) 内所有数字的方差 1 5 4 2 3 2.0000 平均数 \(=\left(1+5+4+2+3\right)\div 5=3\)，方差 \(=\left(\left(1-3\right)^2+\left(5-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=2.0000\)
\(3\) 1 1 1 1 将 \(\left[1,1\right]\) 内所有数字加 \(1\) 2 5 4 2 3 - -
\(4\) 1 2 2 -1 将 \(\left[2,2\right]\) 内所有数字加 \(-1\) 2 4 4 2 3 - -
\(5\) 3 1 5 求 \(\left[1,5\right]\) 内所有数字的方差 2 4 4 2 3 0.8000 平均数 \(=\left(2+4+4+2+3\right)\div 5=3\)，方差 \(=\left(\left(2-3\right)^2+\left(4-3\right)^2+\left(4-3\right)^2+\left(2-3\right)^2+\left(3-3\right)^2\right)\div 5=0.8000\)

数据规模：

数据点 \(N\) \(M\) 备注
\(1\sim3\) \(N\le 8\) \(M\le 15\) -
\(4\sim7\) \(N\le 10^5\) \(M\le 10^5\) 不包含操作 \(3\)
\(8\sim10\) \(N\le 10^5\) \(M\le 10^5\) -
image-20240227172501372 
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
118
119
120
121
122
//本题需要两个懒标记
#include<iostream>
using namespace std;
double a[100010];
struct node 
{
    double sum, lazy;
    //和和懒标记
};
node t1[400010], t2[400010];
void pushup(int rt)
{
    t1[rt].sum = t1[rt << 1].sum + t1[rt << 1 | 1].sum;
    t2[rt].sum = t2[rt << 1].sum + t2[rt << 1 | 1].sum;
    //左儿子和右儿子
}
void build(int rt, int l, int r)
{
    if (l == r) //叶子节点 
    {
        cin>>t1[rt].sum;
        //输入
        t2[rt].sum = t1[rt].sum * t1[rt].sum;
        //和乘法
        return;
    }
    int mid = (l + r) >> 1;
    //构建左右树
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}
void pushdown(int rt, int l, int r)
    //下放左右
{
    int mid = (l + r) >> 1;
    t2[rt << 1].lazy += t2[rt].lazy;
    //加入标记
    //并求和
    t2[rt << 1].sum += t1[rt << 1].sum * (t2[rt].lazy * 2) + (mid - l + 1) * (t2[rt].lazy * t2[rt].lazy);
    t2[rt << 1 | 1].lazy += t2[rt].lazy;
    t2[rt << 1 | 1].sum += t1[rt << 1 | 1].sum * (t2[rt].lazy * 2) + (r - mid) * (t2[rt].lazy * t2[rt].lazy);
    t2[rt].lazy = 0;
    t1[rt << 1].lazy += t1[rt].lazy;
    t1[rt << 1].sum += (mid - l + 1) * t1[rt].lazy;
    t1[rt << 1 | 1].lazy += t1[rt].lazy;
    t1[rt << 1 | 1].sum += (r - mid) * t1[rt].lazy;
    t1[rt].lazy = 0;
}
bool inrange(int L,int R,int l,int r)
{
    return (l<=L)&&(R<=r);
    //判断是否包含
}
bool outrange(int L,int R,int l,int r)
{
    return (L>r)||(R<l);
    //判断两者的交集是否无解
}
double query(node tree[], int rt, int l, int r, int x, int y)
//当前节点为rt,区间为l到r,我们要查询x到y
{
    if(inrange(l,r,x,y)) return tree[rt].sum;
    int mid = (l + r) >> 1;
    if (tree[rt].lazy) 
        pushdown(rt, l, r);
    double ans = 0;
    if (x <= mid) ans = ans + query(tree, rt << 1, l, mid, x, y);
    if (y > mid) ans = ans + query(tree, rt << 1 | 1, mid + 1, r, x, y);
    pushup(rt);
    return ans;
}
void modify(int rt, int l, int r, int x, int y, double z)
//当前节点为rt,区间为l到r，我们把区间x到y的每个值都上z 
{
    if (inrange(l,r,x,y))
    {
        t2[rt].lazy += z;
        t2[rt].sum += t1[rt].sum * (z * 2) + (r - l + 1) * (z * z);
        t1[rt].lazy += z;
        t1[rt].sum += (r - l + 1) * z;
        return;
    }
      else if(!outrange(l,r,x,y))
    {
        int Mid=(l+r)/2;
        pushdown(rt,l,r);
        modify(rt*2,l,Mid,x,y,z);
        modify(rt*2+1,Mid+1,r,x,y,z);
    pushup(rt);
    }

}
int n, m, opt;
int main()
{
    cin>>n>>m;
    build(1, 1, n);
    while (m--)
    {
        cin>>opt;
        if (opt == 1)
        {
            int x, y;
            double z;
            cin>>x>>y>>z;
            modify(1, 1, n, x, y, z);
        }
        if (opt == 2)
        {
            int x, y;
            cin>>x>>y;
            printf("%.4lf\n", query(t1, 1, 1, n, x, y) / ((y - x + 1) * 1.0));
        }
        if (opt == 3)
        {
            int x, y;
            cin>>x>>y;
            printf("%.4lf\n", (query(t2, 1, 1, n, x, y) / ((y - x + 1) * 1.0)) - (query(t1, 1, 1, n, x, y) / ((y - x + 1) * 1.0)) * (query(t1, 1, 1, n, x, y) / ((y - x + 1) * 1.0)));
        }
    }
}

[COCI2010-2011#6] STEP

题目描述

给定一个长度为 \(n\) 的字符序列 \(a\)，初始时序列中全部都是字符 L。

有 \(q\) 次修改，每次给定一个 \(x\)，若 \(a_x\) 为 L，则将 \(a_x\) 修改成 R，否则将 \(a_x\) 修改成 L。

对于一个只含字符 L，R 的字符串 \(s\)，若其中不存在连续的 L 和 R，则称 \(s\) 满足要求。

每次修改后，请输出当前序列 \(a\) 中最长的满足要求的连续子串的长度。

输入格式

第一行有两个整数，分别表示序列的长度 \(n\) 和修改操作的次数 \(q\)。

接下来 \(q\) 行，每行一个整数，表示本次修改的位置 \(x\)。

输出格式

对于每次修改操作，输出一行一个整数表示修改 \(a\) 中最长的满足要求的子串的长度。

样例 #1

样例输入 #1

1
2
3
6 2
2
4

样例输出 #1

1
2
3
5

样例 #2

样例输入 #2

1
2
3
4
5
6
6 5
4
1
1
2
6

样例输出 #2

1
2
3
4
5
3
3
3
5
6

提示

数据规模与约定

对于全部的测试点，保证 \(1 \leq n, q \leq 2 \times 10^5\)，\(1 \leq x \leq n\)。

说明

题目译自 COCI2010-2011 CONTEST #6 T5 STEP，翻译来自 @一扶苏一。

左右前缀区间维护

维护什么呢？

维护以下：

1
2
一个区间的前缀最大01连续子串
一个区间的后缀最大01连续子串
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
#include<bits/stdc++.h>
using namespace std;
const int Len = 3e5+100;
int n,m,opt,a[Len],sum[Len << 2],lsum[Len << 2],rsum[Len << 2]; 
int ls(int x)
{
    return x << 1;
}
int rs(int x)
{
    return x << 1 | 1;
}
void push_up(int p,int l,int r)
{
	int mid = (l + r) >> 1;
	int L = (mid - l + 1),R = r - mid;
	lsum[p] = lsum[ls(p)];
    //父亲最少要等于儿子罢
    rsum[p] = rsum[rs(p)];
    //父亲最少要等于儿子
    sum[p] = max(sum[ls(p)],sum[rs(p)]);
    //区间和至少要是左和右的最大值
	if(a[mid] != a[mid + 1])
	{
        //看端点一致吗
        //如果不一致代表可以更新
		sum[p] = max(sum[p],rsum[ls(p)] + lsum[rs(p)]);
		if(sum[ls(p)] == L) lsum[p] = L + lsum[rs(p)];
		if(sum[rs(p)] == R) rsum[p] = R + rsum[ls(p)];
	} 
}
void build(int p,int l,int r)
{
	sum[p] = lsum[p] = rsum[p] = 1;
    //等于1，初始化建树
    //a一开始都是0，因此绝对建树正确性
	if(l == r) return; 
	int mid = (l + r) >> 1;
	build(ls(p),l,mid);
	build(rs(p),mid + 1,r);
	push_up(p,l,r);
    //上传
}
void update(int p,int l,int r,int idx)
{
	if(l == r && l == idx)
    {
        a[l] ^= 1;
        return;
    }//找到了需要更改的节点 
	int mid = (l + r) >> 1; 
	if(idx <= mid) 
        update(ls(p),l,mid,idx);
	else 
        update(rs(p),mid + 1,r,idx);
	push_up(p,l,r);
} 
int query()
{
    return sum[1];
}
int main()
{
	cin>>n>>m;
	build(1,1,n); 
	while(m --)
	{
		cin>>opt;
		update(1,1,n,opt);
		cout<<query()<<'\n';
	}
	return 0;
}

三元上升子序列

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 \(n\) 个整数的序列 \(a_1,a_2,\ldots,a_n\) 中，三个数被称作thair当且仅当 \(i<j<k\) 且 \(a_i<a_j<a_k\)。

求一个序列中 thair 的个数。

输入格式

开始一行一个正整数 \(n\),

以后一行 \(n\) 个整数 \(a_1,a_2,\ldots,a_n\)。

输出格式

一行一个整数表示 thair 的个数。

样例 #1

样例输入 #1

1
2
4
2 1 3 4

样例输出 #1

1
2

样例 #2

样例输入 #2

1
2
5
1 2 2 3 4

样例输出 #2

1
7

提示

样例2 解释

\(7\) 个 thair 分别是：

  • 1 2 3
  • 1 2 4
  • 1 2 3
  • 1 2 4
  • 1 3 4
  • 2 3 4
  • 2 3 4

数据规模与约定

  • 对于 \(30\%\) 的数据 保证 \(n\le100\)；

  • 对于 \(60\%\) 的数据 保证 \(n\le2000\)；

  • 对于 \(100\%\) 的数据 保证 \(1 \leq n\le3\times10^4\)，\(1\le a_i\leq 10^5\)。

  • 三元上升子序列的个数=每个数前比它小的数的个数*每个数后比它大的数的个数 之和

    用线段树维护

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
int n;
ll ans;
const int N=30001;
struct node
{
int num,pos;
}a[N];
int cnt;
int num[2*N];
int sum[N*4];
int s[2*N];
int b[2*N];
bool cmp (node a,node b)
{
    return a.num<b.num;
}
void push_up(int root)
{
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
void update(int root,int l,int r,int pos)
{
    if(l==r&&l==pos)
    {
        sum[root]++;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=pos) 
    {
        update(root*2,l,mid,pos);
    }
    if(mid<pos) 
    {
        update(root*2+1,mid+1,r,pos);
    }
    push_up(root);
}
int query(int root,int l,int r,int L,int R)
{
    if(L<=l && r<=R) 
    {
        return sum[root];
    }
    int mid=(l+r)>>1;
    int t=0;
    if(mid>=L) t+=query(root*2,l,mid,L,R);
    if(mid<R) t+=query(root*2+1,mid+1,r,L,R);
    return t; 
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].num;
a[i].pos=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) 
{
        if(a[i].num>a[i-1].num) cnt++;
        num[a[i].pos]=cnt; 
}
for(int i=1;i<=n;i++)
{
    if(num[i]>1)
    {
    //就是所谓的排名罢
    s[i]=query(1,1,n,1,num[i]-1);
    }
    update(1,1,n,num[i]);
}
  memset(sum,0,sizeof(sum));
for(int i=n;i>=1;i--)
    {
        if(num[i]<n) b[i]=query(1,1,n,num[i]+1,n);
        update(1,1,n,num[i]);
    }
  for(int i=1;i<=n;i++) 
  {
    ans+=(b[i]*s[i]);
  }
cout<<ans;

}

色板游戏

题目背景

阿宝上学了，今天老师拿来了一块很长的涂色板。

题目描述

色板长度为 \(L\)，\(L\) 是一个正整数，所以我们可以均匀地将它划分成 \(L\) 块 \(1\) 厘米长的小方格。并从左到右标记为 \(1, 2, \dots L\)。

现在色板上只有一个颜色，老师告诉阿宝在色板上只能做两件事：

  1. C A B C 指在 \(A\) 到 \(B\) 号方格中涂上颜色 \(C\)。
  2. P A B 指老师的提问：\(A\) 到 \(B\) 号方格中有几种颜色。

学校的颜料盒中一共有 \(T\) 种颜料。为简便起见，我们把他们标记为 \(1, 2, \dots T\). 开始时色板上原有的颜色就为 \(1\) 号色。 面对如此复杂的问题，阿宝向你求助，你能帮助他吗？

输入格式

第一行有3个整数 \(L (1 \le L \le 10^5), T (1 \le T \le 30) 和 O (1 \le O \le 10^5)\)。 在这里 \(O\) 表示事件数。

接下来 \(O\) 行, 每行以 C A B C 或 P A B 得形式表示所要做的事情（这里 \(A, B, C\) 为整数, 可能 \(A> B\)，这样的话需要你交换 \(A\) 和 \(B\)）。

输出格式

对于老师的提问，做出相应的回答。每行一个整数。

样例 #1

样例输入 #1

1
2
3
4
5
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

样例输出 #1

1
2
2
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
118
119
120
121
122
123
124
125
126
127
128
129
130
//30种颜料，开30棵线段树合理罢
#include <bits/stdc++.h>
using namespace std;
const int T=31,N=100010;
int n,t,m;
int laz[T][N<<2],sum[T][N<<2];
//30棵线段树
void pushup(int i,int x)
{
	sum[i][x]=sum[i][x*2]+sum[i][x*2+1];
}
void build(int i,int x,int l,int r)
{
	if (l==r) 
    {
		sum[i][x]=1;
		//如果l==r,直接为1
		return;
		//直接return
	}
	int mid=l+r>>1;
	build(i,x*2,l,mid);
	build(i,x*2+1,mid+1,r);
	pushup(i,x);
	//建树
}
void pushdown(int i,int x)
{
	if (laz[i][x]==-1) 
    {
		sum[i][x*2]=sum[i][x*2+1]=0;
		laz[i][x*2]=laz[i][x*2+1]=-1;
	}
	//直接为0
	//laz直接变成-1
	else 
    {
		sum[i][x*2]=sum[i][x*2+1]=laz[i][x];
		laz[i][x*2]=laz[i][x*2+1]=laz[i][x];
	}
	//不然的话直接变成左儿子等于右儿子了
	laz[i][x]=0;
}
void change(int i,int x,int l,int r,int ls,int rs,int v)
{
	if (l>rs||r<ls) 
    {
        return;
    }
	if (l>=ls&&r<=rs) 
	{
		sum[i][x]=v;
		if (!v) laz[i][x]=-1;
		else laz[i][x]=v;
		return;
	}
	if (laz[i][x]) 
    {
        pushdown(i,x);
    }
	int mid=l+r>>1;
	if (ls<=mid) 
    {
        change(i,x*2,l,mid,ls,rs,v);
    }
	if (rs>mid) 
    {
        change(i,x*2+1,mid+1,r,ls,rs,v);
    }
	pushup(i,x);
}

int ask(int i,int x,int l,int r,int ls,int rs)
{
	if (l>rs||r<ls) 
    {
        return 0;
    }
	if (l>=ls&&r<=rs) 
    {
        return sum[i][x];
    }
	if (laz[i][x]) 
    {
        pushdown(i,x);
    }
	int mid=l+r>>1;
	return 
    {
        ask(i,x*2,l,mid,ls,rs)+ask(i,x*2+1,mid+1,r,ls,rs);
    }
}
int main()
{
	cin>>n>>t>>m;
	build(1,1,1,n);
	char s[3];int l,r,v;
	for (int i=1;i<=m;++i) 
	{
	cin>>s>>l>>r;
		if (l>r) swap(l,r);
		if (s[0]=='C') 
		{
			cin>>v;
			for (int k=1;k<=t;++k)
				if (k!=v)
                    //如果不是那棵树
                {
                    change(k,1,1,n,l,r,0);
                }
				else 
                    //如果是
                {
                    change(k,1,1,n,l,r,1);
                }
		}
		else 
        {
			int ans=0;
			for (int k=1;k<=t;++k)
				if (ask(k,1,1,n,l,r))
                {
                    //如果那棵树有颜色
                    ++ans;
                }
		cout<<ans<<'\n';
		}
	}
	return 0;
}

[yLOI2019] 棠梨煎雪

题目背景

岁岁花藻檐下共将棠梨煎雪，
自总角至你我某日辗转天边。
天淡天青，宿雨沾襟，
一年一会信笺却只见寥寥数言。

——银临《棠梨煎雪》

题目描述

扶苏正在听《棠梨煎雪》的时候，@spitfirekindergarten 发来一道 IOI2018 集训队作业题：我切了这集训队题，辣鸡扶苏快过来做题。扶苏定睛一看，这不 s* 题嘛，写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费，于是就有了这道题。

歌词中的主人公与她的朋友一年会有一次互相写信给对方，一共通信了 \(m\) 年。为了简化问题，我们认为她们每封信的内容都是一条二进制码，并且所有二进制码的长度都是 \(n\)。即每封信的内容都是一个长度为 \(n\) 的字符串，这个字符串只含字符 0 或 1。

这天她拿出了朋友写给她的所有信件，其中第 \(i\) 年的写的信件编号为 \(i\)。由于信件保存时间过久，上面有一些字符已经模糊不清，我们将这样的位置记为 ?，? 字符可以被解释为 0 或 1。由于她的朋友也是人，符合人类的本质，所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你，对于一段连续的年份区间 \([l,r]\) 中的所有信件，假如朋友在这段时间展示了人类的本质，所写的是同一句话，那么这一句话一共有多少种可能的组成。也即一共有多少字符串 \(S\)，满足在这个区间内的所有信件的内容都可能是 \(S\)。

一个长度为 \(n\) 的只含 0,1,? 的字符串 \(A\) 可能是一个字符串 \(B\) 当且仅当 \(B\) 满足如下条件：

  • \(B\) 的长度也是 \(n\) 。
  • \(B\) 中只含字符 0,1。
  • \(A\) 中所有为 0 的位置在 \(B\) 中也是 0。
  • \(A\) 中所有为 1 的位置在 \(B\) 中也是 1。
  • \(A\) 中为 ? 的位置在 \(B\) 中可以为 0 也可以是 1。

同时她可能会突然发现看错了某年的信的内容，于是她可能会把某一年的信的内容修改为一个别的只含 0,1,? 的长度为 \(n\) 的字符串。

输入格式

每个输入文件中都有且仅有一组测试数据。

输入数据第一行为三个用空格隔开的整数，分别代表代表字符串长度 \(n\)，字符串个数 \(m\) 和操作次数 \(q\)。

下面 \(m\) 行，每行是一个长度为 \(n\) 的字符串，第 \((i + 1)\) 行的字符串 \(s_i\) 代表第 \(i\) 年信的内容。

下面 \(q\) 行，每行的第一个数字是操作编号 \(opt\)。

  • 如果 \(opt=0\)，那么后面接两个整数 \([l,~r]\)，代表一次查询操作。
  • 如果 \(opt=1\)，那么后面接一个整数 \(pos\)，在一个空格后会有一个长度为 \(n\) 的字符串 \(t\)，代表将第 \(pos\) 个字符串修改为新的字符串 \(t\)。

输出格式

为了避免输出过大，请你输出一行一个数代表所有查询的答案异或和对 \(0\) 取异或的结果。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
3 3 5
010
0?0
1?0
0 1 2
0 2 3
1 3 0??
0 2 3
0 1 3

样例输出 #1

1
2

提示

样例 1 解释

  • 对于第一次询问，只有串 010 符合要求。
  • 对于第二次询问，由于第二个串的第一位为 1，第三个串的第一位为 0，故没有串符合要求。
  • 修改后将第三个串修改为 0??。
  • 对于第四次询问，有两个串符合要求，分别为 000 和 010。
  • 对于第五次询问，只有 010 符合要求。

故答案为 \(1,0,2,1\)，他们的异或和再异或 \(0\) 的值为 \(2\)。

数据规模与约定

本题采用多测试点捆绑测试，共有 7 个子任务。

子任务编号 $m = $ $q = $ $n = $ 子任务分数
\(1\) \(1\) \(0\) \(1\) \(5\)
\(2\) \(102\) \(102\) \(10\) \(10\)
\(3\) \(1003\) \(1003\) \(10\) \(15\)
\(4\) \(1004\) \(10004\) \(30\) \(15\)
\(5\) \(100005\) \(500005\) \(1\) \(15\)
\(6\) \(100006\) \(50006\) \(30\) \(10\)
\(7\) \(100007\) \(1000007\) \(30\) \(30\)

对于全部的测试点，保证：

  • \(1 \leq m \leq 10^5 + 7\)，\(0 \leq q \leq 10^6 + 7\)，\(1 \leq n \leq 30\)。
  • \(0 \leq opt \leq 1\)，\(1 \leq pos \leq m\)，\(1 \leq l \leq r \leq m\)。
  • \(s_i, t\) 的长度均为 \(n\) 且只含有字符 0,1,?。
  • 输入字符串的总长度不超过 \(5 \times 10^6\)。数据在 Linux 下生成，即换行符不含 \r。

提示

  • 请注意常数因子对程序效率造成的影响。
  • 请注意数据读入对程序效率造成的影响。
  • 请注意输入的问号为嘤文问号，即其 ASCII 值为 \(63\)

注: 为减少错误做法的通过率，时限于 2020 年 7 月由 2000ms 改为 1500ms

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
#include <bits/stdc++.h>
#define maxn 100100
using  ll= long long;
using namespace std;
ll tree[maxn*4],a[maxn];
int fa[maxn],m,n,q,l,r,t;
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}//并查集，路径压缩
void add(int x,ll y)
{
while(x<=n)
{
tree[x]+=y;
x+=(x&-x);
}
}
ll qry(int x)
{
ll r=0;
while(x)
{
	r+=tree[x];
	x-=(x&-x);
}
return r;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
	cin>>a[i];
	add(i,a[i]);
	fa[i]=i;

}
cin>>m;
fa[n+1]=n+1;
	while(m--)
	{
	cin>>q>>l>>r;
	if (l>r) 
	{
	swap(l,r); 
	}
		if (q==1) 
		{
	cout<<qry(r)-qry(l-1)<<'\n';
		}
		else 
		for (int i=l;i<=r;)
		{
			add(i,(t=sqrt(a[i]))-a[i]);
			a[i]=t;
			fa[i]=a[i]<=1?i+1:i;
			////开方到1后直接把父亲更改为下一个数 
			i=fa[i]==i?i+1:find(fa[i]);
			////如果这个数没有开方到1，到下一个数，否则找下一个为1的数 
						
		}
	}
}

[SCOI2010] 序列操作

题目描述

lxhgww 最近收到了一个 \(01\) 序列，序列里面包含了 \(n\) 个数，下标从 \(0\) 开始。这些数要么是 \(0\)，要么是 \(1\)，现在对于这个序列有五种变换操作和询问操作：

  • 0 l r 把 \([l, r]\) 区间内的所有数全变成 \(0\)；
  • 1 l r 把 \([l, r]\) 区间内的所有数全变成 \(1\)；
  • 2 l r 把 \([l,r]\) 区间内的所有数全部取反，也就是说把所有的 \(0\) 变成 \(1\)，把所有的 \(1\) 变成 \(0\)；
  • 3 l r 询问 \([l, r]\) 区间内总共有多少个 \(1\)；
  • 4 l r 询问 \([l, r]\) 区间内最多有多少个连续的 \(1\)。

对于每一种询问操作，lxhgww 都需要给出回答，聪明的程序员们，你们能帮助他吗？

输入格式

第一行两个正整数 \(n,m\)，表示序列长度与操作个数。
第二行包括 \(n\) 个数，表示序列的初始状态。
接下来 \(m\) 行，每行三个整数，表示一次操作。

输出格式

对于每一个询问操作，输出一行一个数，表示其对应的答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
10 10
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
2 2 2
4 0 4
0 3 6
2 3 7
4 2 8
1 0 5
0 5 6
3 3 9

样例输出 #1

1
2
3
4
5
2
6
5

提示

【数据范围】
对于 \(30\%\) 的数据，\(1\le n,m \le 1000\)；
对于\(100\%\) 的数据，\(1\le n,m \le 10^5\)。

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
#include<bits/stdc++.h>
using ll=long long;
#define rep(i, x, y) for(int i = (x);i <= (y);i++)
using namespace std;
const int N = 200019;
int n,m;
int v[N];
#define lid (id << 1)
#define rid (id << 1) | 1
//定义树维护部分
struct seg_tree
{
    int l, r;
    int sum;//求和
    int lazy;//-1.NULL  0.全为0  1.全为1
	int rev;//翻转标记
    int max[2], lmax[2], rmax[2];
    //max表示最长连续子段
    //lmax表示左开始的最长
    //rmax表示右开始的最长
    //还有0-1，就是代表数字0，1
}tree[N << 2];
//Pushup部分
void pushup(int id)
{
    tree[id].sum = tree[lid].sum + tree[rid].sum;
    //求和标记
    rep(i, 0, 1)
    {
        tree[id].lmax[i] = tree[lid].lmax[i];
        //先赋值一下，后面再改
        if(i == 1 && tree[lid].sum == tree[lid].r - tree[lid].l + 1)
		{
		//左区间全满，且为1的意思
		//那么可以跨越过去加上右区间的左区间了
           
		    tree[id].lmax[i] += tree[rid].lmax[i];//可以跨越
        }
        else if(i == 0 && tree[lid].sum == 0)
		{
		//左区间全空，且为0的意思
		//那么也是同理也可以跨越过去
            tree[id].lmax[i] += tree[rid].lmax[i];
        }
        tree[id].rmax[i] = tree[rid].rmax[i];
        //有病也先赋值一下，后面再改
        if(i == 1 && tree[rid].sum == tree[rid].r - tree[rid].l + 1)
        {
        	//全满且为1，可以加上左区间的右边
		    tree[id].rmax[i] += tree[lid].rmax[i];
		}
        else if(i == 0 && tree[rid].sum == 0)
           {
           	//全满为0，也是一样
		    tree[id].rmax[i] += tree[lid].rmax[i]; 
			}
        tree[id].max[i] = tree[lid].rmax[i] + tree[rid].lmax[i];
		//中间部分，就是左区间的右+右区间的左
        tree[id].max[i] = max(tree[id].max[i], tree[lid].max[i]);
		//继承子区间，和子的最大比一下
        tree[id].max[i] = max(tree[id].max[i], tree[rid].max[i]);
        //继承子区间，和子的最大比一下
        }
    }
    
    
    //建树部分
void build(int id, int l, int r)
{
    tree[id].l = l, tree[id].r = r, tree[id].lazy = -1;
    //一开始的赋值，包括左右和赋值标记
    if(l == r)
    {
        tree[id].sum = v[l];
        //和直接赋值
        tree[id].max[0] = tree[id].lmax[0] = tree[id].rmax[0] = (v[l] == 0);
        tree[id].max[1] = tree[id].lmax[1] = tree[id].rmax[1] = (v[l] == 1);
        //根据是1/0进行赋值
        return ;
        }
    int mid = (l + r) >> 1;
    //建树
    build(lid, l, mid), build(rid, mid + 1, r);
    pushup(id);
    }
void pushdown(int id)
{
    if(tree[id].lazy != -1)
    //赋值标记碾压一切
    {//优先级最高
		tree[id].rev = 0;//清空标记
        int val = tree[id].lazy;
        //定义val
        tree[lid].sum = (tree[lid].r - tree[lid].l + 1) * val;
        tree[rid].sum = (tree[rid].r - tree[rid].l + 1) * val;
        //子树要更新一下和了
        tree[lid].lazy = tree[rid].lazy = val;
		tree[lid].rev = tree[rid].rev = 0;
        //子树的赋值标记跟上，翻转为0
        tree[lid].max[val] 
        = tree[lid].lmax[val] 
        = tree[lid].rmax[val] 
        = tree[lid].r - tree[lid].l + 1;
        tree[lid].max[val ^ 1] 
        = tree[lid].lmax[val ^ 1] 
        = tree[lid].rmax[val ^ 1] 
        = 0;
        //左子树的赋值0/1区间的更改
        
        tree[rid].max[val] 
        = tree[rid].lmax[val] 
        = tree[rid].rmax[val] 
        = tree[rid].r - tree[rid].l + 1;
        tree[rid].max[val ^ 1] 
        = tree[rid].lmax[val ^ 1] 
        = tree[rid].rmax[val ^ 1] 
        = 0;
         //右子树的赋值0/1区间的更改

		tree[id].lazy = -1;
		//清空
        }
    if(tree[id].rev)
    //翻转标记
    {
        tree[lid].sum = (tree[lid].r - tree[lid].l + 1) - tree[lid].sum;
        //和肯定得改了
        tree[rid].sum = (tree[rid].r - tree[rid].l + 1) - tree[rid].sum;
        //和要改
        if(tree[lid].lazy != -1)tree[lid].lazy ^= 1;
		//如果有赋值标记，证明是之前的,或0，或1，0->1,1->0
		else tree[lid].rev ^= 1;
		//不然子树翻转标记直接翻转
		if(tree[rid].lazy != -1)tree[rid].lazy ^= 1;
		else tree[rid].rev ^= 1;
		//右子树同理
        
        swap(tree[lid].max[0], tree[lid].max[1]);
        swap(tree[lid].lmax[0], tree[lid].lmax[1]);
        swap(tree[lid].rmax[0], tree[lid].rmax[1]);
        
        swap(tree[rid].max[0], tree[rid].max[1]);
        swap(tree[rid].lmax[0], tree[rid].lmax[1]);
        swap(tree[rid].rmax[0], tree[rid].rmax[1]);
		//由于翻转，左右子树都要换
		tree[id].rev = 0;
        }
    }
void update(int id, int val, int l, int r)
{
    pushdown(id);
    //下放
    if(tree[id].l == l && tree[id].r == r)
    {
        if(val == 0 || val == 1)
        {
            tree[id].sum = (tree[id].r - tree[id].l + 1) * val;
            //更新和
            tree[id].lazy = val;
            //更新懒标记
            tree[id].max[val] 
            = tree[id].lmax[val] 
            = tree[id].rmax[val] 
            = tree[id].r - tree[id].l + 1;
            //都更新罢，毕竟是赋值
            tree[id].max[val ^ 1] 
            = tree[id].lmax[val ^ 1] 
            = tree[id].rmax[val ^ 1] 
            = 0;
            //相反的都更新为0
            }
        else if(val == 2)
        {
        	//2的话就是取反了，都交换即可
            tree[id].sum = (tree[id].r - tree[id].l + 1) - tree[id].sum;
            tree[id].rev ^= 1;
            swap(tree[id].max[0], tree[id].max[1]);
            swap(tree[id].lmax[0], tree[id].lmax[1]);
            swap(tree[id].rmax[0], tree[id].rmax[1]);
            }
        return ;
        }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if(mid < l)update(rid, val, l, r);
    else if(mid >= r)update(lid, val, l, r);
    else update(lid, val, l, mid), update(rid, val, mid + 1, r);
    pushup(id);
    //直接分快+上推
    }
int query(int id, int l, int r)
{
    pushdown(id);
    if(tree[id].l == l && tree[id].r == r)
	{
	return tree[id].sum;
	//查询和
	}
    int mid = (tree[id].l + tree[id].r) >> 1;
    if(mid < l)return query(rid, l, r);
    else if(mid >= r)return query(lid, l, r);
    else return query(lid, l, mid) + query(rid, mid + 1, r);
    //都是普通的线段树了
    }
//查询最长的1来了
seg_tree Q_max(int id, int l, int r)
{
    pushdown(id);
    if(tree[id].l == l && tree[id].r == r)
        return tree[id];
    int mid = (tree[id].l + tree[id].r) >> 1;
    if(mid < l)return Q_max(rid, l, r);
    else if(mid >= r)return Q_max(lid, l, r);
    //查左查右，不然就是中间了
    else
    {
    	//这里代码和上面几乎一样
        seg_tree ret, L = Q_max(lid, l, mid), R = Q_max(rid, mid + 1, r);
        ret.sum = L.sum + R.sum;
        rep(i, 0, 1){
            ret.lmax[i] = L.lmax[i];
            if(i == 1 && L.sum == L.r - L.l + 1)
			//左区间全满
                ret.lmax[i] += R.lmax[i];
				//可以跨越
            else if(i == 0 && L.sum == 0)
			//左区间全空
                ret.lmax[i] += R.lmax[i];
            
            ret.rmax[i] = R.rmax[i];
            if(i == 1 && R.sum == R.r - R.l + 1)
                ret.rmax[i] += L.rmax[i];
            else if(i == 0 && R.sum == 0)
                ret.rmax[i] += L.rmax[i];
            
            ret.max[i] = L.rmax[i] + R.lmax[i];
			//中间
            ret.max[i] = max(ret.max[i], L.max[i]);
			//继承子区间
            ret.max[i] = max(ret.max[i], R.max[i]);
            //继承子区间
            }
        return ret;
        }
    }
int main(){
    cin>>n>>m;
    rep(i, 1, n)cin>>v[i];
    build(1, 1, n);
    while(m--)
    {
        int cmd , l , r;
        cin>>cmd>>l>>r;
        l++, r++;
        if(cmd == 0)
		{
		update(1, 0, l, r);
		}	
        else if(cmd == 1)
		{
		update(1, 1, l, r);
		}	
        else if(cmd == 2)
		{
		update(1, 2, l, r);
		}	
        else if(cmd == 3)
		{
		cout<<query(1, l, r)<<'\n';
		}	
        else 
		{
		cout<<Q_max(1, l, r).max[1]<<'\n';
		}
        }
    return 0;
    }