NEFU大一暑假集训-线段树

题集链接

OP

感谢学长的讲解与付出；

感谢ph和zsl两位大佬的指导与讨论；

夹带私货：
此节课的代表性的内容已经整理到自己的贴子中：【笔记】数据结构

线段树本身相对抽象，一些题又有懒标记的要求，实在不太好理解；
从应用来讲，线段树可以快速地进行区间修改与区间查询，但是所需空间复杂度比较大，有时需要离散化处理；

A Lowbit

参考

思路

朴素来讲，我们会在进行区间更改时递归到所有叶节点进行lowbit更改，但是这种做法会被卡T；

我们可以发现，若某叶节点元素 a 满足lowbit(a)=alowbit(a)=a，则a+lowbit(a)=2aa+lowbit(a)=2a，并且lowbit(a)=alowbit(a)=a的性质不会改变；
除此之外，若某节点 s 下所有叶节点元素 a 均满足lowbit(a)=alowbit(a)=a，则对 s 区间进行操作后，等价与2s2s，并且lowbit(a)=alowbit(a)=a的性质也不会改变；

我们可以用此性质，懒标记存储此节点有多少次二倍操作未下传，就可以一定程度上降低时间复杂度；

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5;
const int M = 998244353;
struct
{
    int l, r, is; //l,r为节点的左右界
    ll sum, lt;   //sum为节点值，lt为懒标记
} segt[N << 2 | 1];
ll qm(ll a,ll b)//qm即quick_mod
{
	ll ans=1%M;//特殊处理M=1这一特殊情况
	for(;b;b>>=1)
	{
		if(b&1)ans=a*ans%M;//如果b此位为1
		a=a*a%M;
	}
	return ans;
}
ll lowbit(ll x) { return x & -x; }
bool check(ll x) { return !(x - lowbit(x)); }
void pushdown(int p) //对懒标记进行下传
{
    if (segt[p].lt)
    {
        segt[p << 1].sum=segt[p << 1].sum*qm(2,segt[p].lt)%M;
        segt[p << 1|1].sum=segt[p << 1|1].sum*qm(2,segt[p].lt)%M;
        segt[p << 1].lt+=segt[p].lt;
        segt[p << 1|1].lt+=segt[p].lt;
        segt[p].lt = 0;
    }
    return;
}
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0, segt[p].is = 0;
    if (cl == cr)
    {
        scanf("%lld", &segt[p].sum);
        segt[p].is = check(segt[p].sum);
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
    segt[p].is = segt[p<<1].is&&segt[p<<1|1].is;
    if (segt[p].is)
        segt[p].sum %= M;
}
void icg(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr && segt[p].is)
    {
        segt[p].sum <<= 1;
        segt[p].lt++;
        segt[p].sum %= M;
        return;
    }
    if (segt[p].l == segt[p].r)
    {
        segt[p].sum += lowbit(segt[p].sum);
        segt[p].is = check(segt[p].sum);
        if (segt[p].is)
            segt[p].sum %= M;
        return;
    }
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    if (cl <= mid)
        icg(p << 1, cl, cr);
    if (cr >= mid + 1)
        icg(p << 1 | 1, cl, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
    segt[p].is = segt[p<<1].is&&segt[p<<1|1].is;
    segt[p].sum %= M;
}
ll ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val += ick(p << 1, cl, cr), val %= M;
    if (cr >= mid + 1)
        val += ick(p << 1 | 1, cl, cr), val %= M;
    return val;
}
int main()
{
    int n, t, q, l, r, o;
    cin >> t;
    while (t--)
    {
        scanf("%d", &n);
        build(1, 1, n);
        scanf("%d", &q);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d%d", &o, &l, &r);
            if (o == 1)
            {
                icg(1, l, r);
            }
            else if (o == 2)
            {
                printf("%lld\n", ick(1, l, r));
            }
        }
    }
}

B Ezzat and Grid

参考
线段树+dp

思路

首先左右界的数据范围过大，需要离散化处理；

定义dp函数dp[i]dp[i]为以第i行为末尾的最长可行序列长度，在线段树内存储结点下前i-1行该节点内的dp[i]dp[i]最大值；
对于某一行的若干的区间，假设有区间内的可行序列长度最大值为a，则有dp[i]=a+1dp[i]=a+1；
同时持续更新答案的最大值（即dp[i]dp[i]）即可；

但是此题要求输出应被删掉的点，就需要在维护线段树时同时记录该最大值对应的行号，在进行dp[i]dp[i]的修改时同时标记fa[i]fa[i]即可；
再通过上溯找到没有在这个序列中的点即可；

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 6e5;
const int M = 998244353;
struct
{
    int l, r; //l,r为节点的左右界
    ll lt;    //sum为节点值，lt为懒标记
    pair<ll, int> sum;
} segt[N << 2 | 1];
map<int, int> mp;
int c = 0, ch = 1, gh[600005];
int dp[300005], fa[300005];
void pushdown(int p) //对懒标记进行下传
{
    if (segt[p].lt)
    {
        segt[p << 1].sum = segt[p].sum;
        segt[p << 1 | 1].sum = segt[p].sum;
        segt[p << 1].lt = segt[p << 1 | 1].lt = 1;
        segt[p].lt = 0;
    }
    return;
}
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = {0, 0};
    if (cl == cr)
    {
        //scanf("%lld", &segt[p].sum);
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = max(segt[p << 1].sum, segt[p << 1 | 1].sum);
}
void icg(int p, int cl, int cr, pair<ll, int> d)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
    {
        if (d >= segt[p].sum)
            segt[p].sum = d, segt[p].lt = 1;
        return;
    }
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    if (cl <= mid)
        icg(p << 1, cl, cr, d);
    if (cr >= mid + 1)
        icg(p << 1 | 1, cl, cr, d);
    segt[p].sum = max(segt[p << 1].sum, segt[p << 1 | 1].sum);
}
pair<ll, int> ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    pair<ll, int> val = {0, 0};
    if (cl <= mid)
        val = max(val, ick(p << 1, cl, cr));
    if (cr >= mid + 1)
        val = max(val, ick(p << 1 | 1, cl, cr));
    return val;
}
pair<int, pair<int, int>> opt;
vector<pair<int, int>> iq[300005];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &opt.first, &opt.second.first, &opt.second.second);
        gh[c++] = opt.second.first;
        gh[c++] = opt.second.second;
        iq[opt.first].push_back(opt.second);
    }
    sort(gh, gh + c);
    mp[gh[0]] = ch++;
    for (int i = 1; i < c; i++)
    {
        if (gh[i] == gh[i - 1])
            continue;
        mp[gh[i]] = ch++;
    }
    build(1, 1, ch);
    int ans = 0, tail = 0;
    for (int i = 1; i <= n; i++)
    {

        pair<ll, int> mx = {0, 0};
        for (int j = 0; j < iq[i].size(); j++)
        {
            pair<ll, int> g = ick(1, mp[iq[i][j].first], mp[iq[i][j].second]);
            if (g > mx)
                mx = g;
        }
        dp[i] = mx.first + 1;
        fa[i] = mx.second;
        if (dp[i] > ans)
        {
            ans = dp[i];
            tail = i;
        }
        for (int j = 0; j < iq[i].size(); j++)
        {
            icg(1, mp[iq[i][j].first], mp[iq[i][j].second], {dp[i], i});
        }
    }
    printf("%d", n - ans);
    if (ans != n)
    {
        printf("\n");
        int now = tail, p = n;
        while (p != now)
            {
                printf("%d ", p--);
            }
        while (1)
        {
            p--;
            now = fa[now];
            while (p != now)
            {
                printf("%d ", p--);
            }
            if(!now)break;
        }
    }
}

C 奇数国

参考

思路

朴素来讲，我们可以在维护乘积线段树的同时，用一个桶数组维护结点的乘积值内有什么质数，有st[p].pri[i]=st[p<<1].pri[i] ∣ st[p<<1∣1].pri[i]st[p].pri[i]=st[p<<1].pri[i]\ |\ st[p<<1|1].pri[i]；

但是如此存储的话，时间即为60n⋅log⁡n60n\cdotp \log n，约为7e77e7，比较悬；

但是仔细观察，60个质数的存在性不必用数组维护，还可以用long long内的数位维护，用[(st[p].pri>>i)&1][(st[p].pri>>i)\&1]表示p结点下是否有质数pip_i，更新时变成了st[p].pri=st[p<<1].pri ∣ st[p<<1∣1].prist[p].pri=st[p<<1].pri\ |\ st[p<<1|1].pri，时间复杂度降低啦；

最后结合快速幂和逆元进行欧拉函数值的求取即可；

代码

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 <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
typedef long long ll;
using namespace std;
const ll M = 19961993;
const int N = 1e5;
struct
{
    int l, r;     //l,r为节点的左右界
    ll sum, ppos; //sum为节点值
} segt[N << 2 | 1];
int pri[62] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
               41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
               101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
               151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
               211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281};

ll qm(ll a, ll b)
{
    ll ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % M;
        a = a * a % M;
    }
    return ans;
}
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].ppos = 2, segt[p].sum = 0;
    if (cl == cr)
    {
        segt[p].sum = 3;
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = (segt[p << 1].sum * segt[p << 1 | 1].sum) % M;
}
void pcg(int p, int x, ll v, ll pnow)
{
    if (segt[p].l == segt[p].r)
    {
        segt[p].sum = v;
        segt[p].ppos = pnow;
        return;
    }
    int mid = segt[p].l + segt[p].r >> 1;
    if (x <= mid)
        pcg(p << 1, x, v, pnow);
    else
        pcg(p << 1 | 1, x, v, pnow);
    segt[p].sum = (segt[p << 1].sum * segt[p << 1 | 1].sum) % M;
    segt[p].ppos = segt[p << 1].ppos | segt[p << 1 | 1].ppos;
}
pair<ll, ll> ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return {segt[p].sum, segt[p].ppos};
    int mid = segt[p].r + segt[p].l >> 1;
    pair<ll, ll> val = {1, 0}, tmp = {0, 0};
    if (cl <= mid)
    {
        tmp = ick(p << 1, cl, cr);
        val.first = val.first*tmp.first%M;
        val.second |= tmp.second;
    }
    if (cr >= mid + 1)
    {
        tmp = ick(p << 1 | 1, cl, cr);
        val.first = val.first*tmp.first%M;
        val.second |= tmp.second;
    }
    val.first%=M;
    return val;
}
int main()
{
    int n = 100000, m;
    ll a, b, c;
    scanf("%d", &m);
    build(1,1,n);
    while (m--)
    {
        scanf("%lld%lld%lld",&a,&b,&c);
        if(!a)
        {
            pair<ll, ll>tmp=ick(1,b,c);
            ll ans=tmp.first;
            for(int i=0;i<60;i++)
            {
                if((tmp.second>>i)&1ll)
                {
                    ans=(ans-(ans*qm(pri[i],M-2))%M+M)%M;
                }
            }
            printf("%lld\n",ans);
        }
        else
        {
            ll pnow=0;
            for(int i=0;i<60;i++)
            {
                if(c%pri[i]==0)pnow|=(1ll<<i);
            }
            pcg(1,b,c,pnow);
        }
    }
    return 0;
}

D 敌兵布阵

思路

板~

单点修改，区间查询

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N = 1e5 + 5;
struct
{
    int l, r;//l,r为节点的左右界
    ll sum, lt;//sum为节点值，lt为懒标记
} segt[N << 2];
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0;
    if (cl == cr)
    {
        scanf("%lld",&segt[p].sum);
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}
void pcg(int p, int x, ll v)//不兼容懒标记
{
    if (segt[p].l == segt[p].r)
    {
        segt[p].sum += v;
        return;
    }
    int mid = segt[p].l + segt[p].r >> 1;
    if (x <= mid)
        pcg(p << 1, x, v);
    else
        pcg(p << 1 | 1, x, v);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}
ll ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val += ick(p << 1, cl, cr);
    if (cr >= mid + 1)
        val += ick(p << 1 | 1, cl, cr);
    return val;
}

int main()
{
    int t,n,a,b,c=1;
    cin>>t;
    while(t--)
    {
        printf("Case %d:\n",c++);
        scanf("%d",&n);
        build(1,1,n);
        string o;
        while(cin>>o&&o!="End")
        {
            scanf("%d%d",&a,&b);
            if(o=="Query")
            {
                printf("%lld\n",ick(1,a,b));
            }
            else if(o=="Add")
            {
                pcg(1,a,b);
            }
            else if(o=="Sub")
            {
                pcg(1,a,-b);
            }
        }
    }
}

E I Hate It

思路

板~

单点修改，区间查询

代码

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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N = 2e5;
struct
{
    int l, r;//l,r为节点的左右界
    ll sum, lt;//sum为节点值，lt为懒标记
} segt[N << 2|1];
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0;
    if (cl == cr)
    {
        scanf("%lld",&segt[p].sum);
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = max(segt[p << 1].sum , segt[p << 1 | 1].sum);
}
void pcg(int p, int x, ll v)//不兼容懒标记
{
    if (segt[p].l == segt[p].r)
    {
        segt[p].sum = v;
        return;
    }
    int mid = segt[p].l + segt[p].r >> 1;
    if (x <= mid)
        pcg(p << 1, x, v);
    else
        pcg(p << 1 | 1, x, v);
    segt[p].sum =max(segt[p << 1].sum , segt[p << 1 | 1].sum);
}
ll ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val=max(val, ick(p << 1, cl, cr));
    if (cr >= mid + 1)
        val=max(val, ick(p << 1 | 1, cl, cr));
    return val;
}

int main()
{
    int m,n,a,b;
    while(~scanf("%d%d",&n,&m))
    {
        build(1,1,n);
        char o;
        while(m--)
        {
            cin>>o;
            scanf("%d%d",&a,&b);
            if(o=='Q')
            {
                printf("%lld\n",ick(1,a,b));
            }
            else if(o=='U')
            {
                pcg(1,a,b);
            }
        }
    }
}

F Transformation

思路

p\in\{1,2,3\}$$朴素来讲，我们可以使用三个懒标记和三个值维护未下传的区间加（ad），区间乘（mu），区间更改（cg）操作和区间下的元素和（sum1），元素平方和（sum2），区间立方和（sum3）； 但是我们就面临一个问题，如果某位同时存在多种标记，如何判断它们的先后顺序？ 在查阅资料时发现，有人在更新时选择先把当前结点的其他标记下传，但是被卡t了； 我们可以制定以下策略： 1. 对某结点进行cg操作时，直接修改三个sum值，清空ad和mu标记； 2. 对某结点进行mu操作时（假设区间乘d），维护三个sum值，对现有的ad标记乘d，mu标记也乘d； 3. 对某节点进行ad操作时（假设区间加d），通过 完全平方公式 和 完全立方公式 维护三个num值，对现有ad标记加d； 以此策略进行维护后，在下传懒标记时只需要以cg，mu，ad的顺序修改子节点就可以规避顺序问题； #### 代码 
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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
typedef long long ll;
using namespace std;
const int M = 10007;
const int N = 1e5;
struct
{
    int l, r;                        //l,r为节点的左右界
    ll sum1, sum2, sum3, ad, mu, cg; //sum为节点值
} segt[N << 2 | 1];
void cgcg(int p, ll d)
{
    segt[p].sum1 = d * (segt[p].r - segt[p].l + 1) % M;
    segt[p].sum2 = d * d * (segt[p].r - segt[p].l + 1) % M;
    segt[p].sum3 = d * d * d * (segt[p].r - segt[p].l + 1) % M;
    segt[p].cg = d;
    segt[p].ad = 0;
    segt[p].mu = 1;
}
void cgmu(int p, ll d)
{
    segt[p].sum1 = segt[p].sum1 * d % M;
    segt[p].sum2 = segt[p].sum2 * d * d % M;
    segt[p].sum3 = segt[p].sum3 * d * d * d % M;
    segt[p].ad = segt[p].ad * d % M;
    segt[p].mu = segt[p].mu * d % M;
}
void cgad(int p, ll d)
{
    int lenp = segt[p].r - segt[p].l + 1;
    segt[p].sum3 = (segt[p].sum3 + lenp * d * d * d + 3 * segt[p].sum1 * d * d + 3 * segt[p].sum2 * d) % M;
    segt[p].sum2 = (segt[p].sum2 + lenp * d * d + 2 * segt[p].sum1 * d) % M;
    segt[p].sum1 = (segt[p].sum1 + lenp * d) % M;
    segt[p].ad = (segt[p].ad + d) % M;
}
void pushdown(int p) //对懒标记进行下传
{
    if (segt[p].cg)
    {
        cgcg(p << 1, segt[p].cg);
        cgcg(p << 1 | 1, segt[p].cg);
        segt[p].cg = 0;
    }
    if (segt[p].mu != 1)
    {
        cgmu(p << 1, segt[p].mu);
        cgmu(p << 1 | 1, segt[p].mu);
        segt[p].mu = 1;
    }
    if (segt[p].ad)
    {
        cgad(p << 1, segt[p].ad);
        cgad(p << 1 | 1, segt[p].ad);
        segt[p].ad = 0;
    }
}
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr;
    segt[p].sum1 = 0, segt[p].sum2 = 0, segt[p].sum3 = 0;
    segt[p].ad = 0, segt[p].mu = 1, segt[p].cg = 0;
    if (cl == cr)
    {
        //scanf("%lld", &segt[p].sum);
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
}
void icg(int p, int cl, int cr, int o, ll d)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
    {
        if (o == 1)
        {
            cgad(p, d);
        }
        else if (o == 2)
        {
            cgmu(p, d);
        }
        else if (o == 3)
        {
            cgcg(p, d);
        }
        return;
    }
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    if (cl <= mid)
        icg(p << 1, cl, cr, o, d);
    if (cr >= mid + 1)
        icg(p << 1 | 1, cl, cr, o, d);
    segt[p].sum1 = (segt[p << 1].sum1 + segt[p << 1 | 1].sum1) % M;
    segt[p].sum2 = (segt[p << 1].sum2 + segt[p << 1 | 1].sum2) % M;
    segt[p].sum3 = (segt[p << 1].sum3 + segt[p << 1 | 1].sum3) % M;
}
ll ick(int p, int cl, int cr, int k)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
    {
        if (k == 1)
            return segt[p].sum1;
        else if (k == 2)
            return segt[p].sum2;
        else if (k == 3)
            return segt[p].sum3;
    }
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val += ick(p << 1, cl, cr, k);
    if (cr >= mid + 1)
        val += ick(p << 1 | 1, cl, cr, k);
    return val % M;
}

int main()
{
    int n, m, x, y, d, o;
    while (~scanf("%d%d", &n, &m) && (n || m))
    {
        build(1, 1, n);
        while (m--)
        {
            scanf("%d%d%d%d", &o, &x, &y, &d);
            if(o!=4)
            {
                icg(1,x,y,o,d);
            }
            else
            {
                printf("%lld\n",ick(1,x,y,d));
            }
        }
    }
    return 0;
}
## G Can you answer these queries? #### 思路 朴素地想，对于一次修改，递归到叶节点进行平方根操作，很不幸，会卡时间； 但是我们可以发现，如果某叶节点的值若为1或0，则进行平方根修改并不能影响其的值； 这样就可以进行标记，如果某节点下所有点都是1或0，则不需要对其进行修改，降低了复杂度； 这道题很坑的一点是，区间左右界的相对大小并不明确，需要修正非法数据； #### 代码 
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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
struct
{
    int l, r;   //l,r为节点的左右界
    ll sum, lt; //sum为节点值，lt为懒标记
} segt[N << 2];
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0;
    if (cl == cr)
    {
        scanf("%lld", &segt[p].sum);
        segt[p].lt = segt[p].sum <= 1;
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
    segt[p].lt = (segt[p << 1].lt == 1 && segt[p << 1 | 1].lt == 1);
}
void icg(int p, int cl, int cr)
{
    if (segt[p].lt)
        return;
    if (segt[p].l == segt[p].r)
    {
        segt[p].sum = (ll)sqrt(segt[p].sum*1.0);
        segt[p].lt = segt[p].sum <= 1;
        return;
    }
    int mid = segt[p].r + segt[p].l >> 1;
    if (cl <= mid)
        icg(p << 1, cl, cr);
    if (cr >= mid + 1)
        icg(p << 1 | 1, cl, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
    segt[p].lt = (segt[p << 1].lt == 1 && segt[p << 1 | 1].lt == 1);
}
ll ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val += ick(p << 1, cl, cr);
    if (cr >= mid + 1)
        val += ick(p << 1 | 1, cl, cr);
    return val;
}

int main()
{
    int n, q, l, r, k, c = 1;
    while (~scanf("%d", &n))
    {
        printf("Case #%d:\n", c++);
        build(1, 1, n);
        scanf("%d", &q);
        for (int i = 1; i <= q; i++)
        {
            scanf("%d%d%d", &k, &l, &r);
            if(l>r)swap(l,r);
            if (k == 0)
                icg(1, l, r);
            else if (k == 1)
                printf("%lld\n", ick(1, l, r));
        }
        printf("\n");
    }
}

## H A Simple Problem with Integers #### 思路 板~ 区间修改，区间查询； #### 代码 
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
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5;
struct
{
    int l, r;//l,r为节点的左右界
    ll sum, lt;//sum为节点值，lt为懒标记
} segt[N << 2 | 1];
void pushdown(int p)//对懒标记进行下传
{
    if (segt[p].lt)
    {
        segt[p << 1].sum += segt[p].lt * (segt[p << 1].r - segt[p << 1].l + 1);
        segt[p << 1 | 1].sum += segt[p].lt * (segt[p << 1 | 1].r - segt[p << 1 | 1].l + 1);
        segt[p << 1].lt += segt[p].lt;
        segt[p << 1 | 1].lt += segt[p].lt;
        segt[p].lt = 0;
    }
}
void build(int p, int cl, int cr)
{
    segt[p].l = cl, segt[p].r = cr, segt[p].lt = 0, segt[p].sum = 0;
    if (cl == cr)
    {
        scanf("%lld", &segt[p].sum);
        return;
    }
    int mid = cl + cr >> 1;
    build(p << 1, cl, mid);
    build(p << 1 | 1, mid + 1, cr);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}

void icg(int p, int cl, int cr, ll d)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
    {
        segt[p].sum += d * (segt[p].r - segt[p].l + 1);
        segt[p].lt += d;
        return;
    }
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    if (cl <= mid)
        icg(p << 1, cl, cr, d);
    if (cr >= mid + 1)
        icg(p << 1 | 1, cl, cr, d);
    segt[p].sum = segt[p << 1].sum + segt[p << 1 | 1].sum;
}

ll ick(int p, int cl, int cr)
{
    if (cl <= segt[p].l && segt[p].r <= cr)
        return segt[p].sum;
    pushdown(p);
    int mid = segt[p].r + segt[p].l >> 1;
    ll val = 0;
    if (cl <= mid)
        val += ick(p << 1, cl, cr);
    if (cr >= mid + 1)
        val += ick(p << 1 | 1, cl, cr);
    return val;
}


int main()
{
    int n, q, l, r, k;
    char o;
    while (~scanf("%d%d", &n,&q))
    {
        build(1, 1, n);
        for (int i = 1; i <= q; i++)
        {
            cin>>o;
            if(o=='C')
            {
                scanf("%d%d%d",&l,&r,&k);
                icg(1,l,r,k);
            }
            else if(o=='Q')
            {
                scanf("%d%d",&l,&r);
                printf("%lld\n",ick(1,l,r));
            }
        }
    }
}
## ED \
算法竞赛 > 比赛与题集
NEFU大一暑假集训-线段树
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-线段树/
作者
F Juny
发布于
2021年8月28日
许可协议