devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

线段树洛谷题单_洛谷线段树简单题

作者：花生_TL007 | 2024-03-02 11:03:52

赞

踩

洛谷线段树简单题

Limit の线段树题单 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

线段树题单

线段树入门

P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间修改+区间求和

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
int n, m;
int a[MAXN];

struct Tr{
    int l, r;
    ll sum, lazy;
}tr[MAXN * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    int lazy = tr[u].lazy;
    if(lazy)
    {
        tr[u << 1].lazy += lazy;
        tr[u << 1 | 1].lazy += lazy;
        tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * lazy;
        tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * lazy;
        tr[u].lazy = 0;
    }
}

void build(int root, int l, int r)
{
    tr[root].l = l, tr[root].r = r; // 注意这边赋值
    if(l == r)
    {
        tr[root].sum = a[l]; // 注意这边
        return;
    }
    int mid = (l + r) >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    pushup(root);
}

void change(int u, int l, int r, int k)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].lazy += k;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k; // 区间求和只需要当前区间加上k
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) change(u << 1, l, r, k);
    if(r > mid) change(u << 1 | 1, l, r, k);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll sum = 0;
    if(l <= mid) sum += query(u << 1, l, r);
    if(r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);

    while(m--)
    {
        int op;
        scanf("%d", &op);
        if(op == 1) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            change(1, l, r, k);
        }
        else {
            int l, r;
            scanf("%d%d", &l, &r);
            ll ans = query(1, l, r);
            printf("%lld\n", ans);
        }
    }

    return 0;
}

/*
5 5
1 5 2 4 3
2 2 4
*/

  • 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

P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[P2023 AHOI2009] 维护序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间加法+区间乘法+区间求和

注意几个点：

  1. 求区间和的时候先算乘法再算加法
  2. 在每一次加法更新的时候，要把乘法一并带上（包括乘法中的return与pushdown）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
int n, m, p;

int a[MAXN];
struct Tr{
    int l, r;
    ll sum, alz, mlz;
}tr[MAXN * 4];

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void pushdown(int u)
{
    tr[u << 1].sum = (tr[u << 1].sum * tr[u].mlz % p + (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].alz % p) % p;
    tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum * tr[u].mlz % p + (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].alz % p) % p;

    tr[u << 1].mlz = (tr[u << 1].mlz * tr[u].mlz) % p;
    tr[u << 1 | 1].mlz = (tr[u << 1 | 1].mlz * tr[u].mlz) % p;

    tr[u << 1].alz = (tr[u << 1].alz * tr[u].mlz % p + tr[u].alz) % p;
    tr[u << 1 | 1].alz = (tr[u << 1 | 1].alz * tr[u].mlz % p + tr[u].alz) % p;

    tr[u].alz = 0;
    tr[u].mlz = 1;
}


void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0, 1};
    if(l == r)
    {
        tr[u].sum = a[l] % p;
        return ;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void add(int u, int l, int r, int k)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].alz = (tr[u].alz + k) % p;
        tr[u].sum = (tr[u].sum + (tr[u].r - tr[u].l + 1) * k % p) % p;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) add(u << 1, l, r, k);
    if(r > mid) add(u << 1 | 1, l, r, k);
    pushup(u);
}

void mul(int u, int l, int r, int k)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].alz = (tr[u].alz * k) % p;
        tr[u].mlz = (tr[u].mlz * k) % p;
        tr[u].sum = (tr[u].sum * k) % p;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) mul(u << 1, l, r, k);
    if(r > mid) mul(u << 1 | 1, l, r, k);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    pushdown(u);
    ll sum = 0;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) sum += query(u << 1, l, r);
    if(r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
    return sum % p;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    build(1, 1, n);
    while(m--)
    {
        int op, l, r, k;
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d%d", &l, &r, &k);
            mul(1, l, r, k);
        }
        else if(op == 2)
        {
            scanf("%d%d%d", &l, &r, &k);
            add(1, l, r, k);
        }
        else {
            scanf("%d%d", &l, &r);
            ll ans = query(1, l, r);
            printf("%lld\n", ans);
        }
    }

    return 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
  • 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

P1531 I Hate It - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

单点修改 + 区间询问

[P1047 NOIP2005 普及组] 校门外的树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间修改 + 查询

类似于维护区间和 ， 标记下放的时候也就是sum清空，标记改变。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int MAXN = 10050;
int n, m;

struct node{
    int l, r;
    int lazy, sum;
}tr[MAXN * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 1};
    if(l == r)
    {
        tr[u].sum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void pushdown(int u)
{
    tr[u << 1].sum = 0;
    tr[u << 1 | 1].sum = 0;

    tr[u << 1].lazy = 0;
    tr[u << 1 | 1].lazy = 0;

}

void change(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].sum = 0;
        tr[u].lazy = 0;
        return;
    }
    if(!tr[u].lazy) pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) change(u << 1, l, r);
    if(r > mid) change(u << 1 | 1, l, r);
    pushup(u);
}

int main()
{
    scanf("%d%d", &n, &m);
    build(1, 1, n + 1);
    while(m -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x ++, y ++;
        change(1, x, y);
    }
    printf("%d\n", tr[1].sum);
    return 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

[P5057 CQOI2006]简单题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

线段树维护当前区间改变的次数（维护异或），异或1即可。

pushdown的时候就改变两个子节点，自己归0即可

void down(int u)
{
    if(t[u].lazy)
    {
        tr[u << 1] ^= 1;
        tr[u << 1 | 1] ^= 1;
        tr[u]=0;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
Tip

但是这道题貌似可以用差分树状数组。

树状数组维护差分序列，每次修改 l l l与 r + 1 r+1 r+1

设d[x] 为从1到x每一个数的总和

假设初始一串数据 0 0 0 0 0 （共五个）

我们要将（1，3）反过来，我们就可以将第一个数加上1，即：

1 0 0 0 0

然后我们在将第四个数加上1，即：

1 0 0 1 0

然后我们可以发现：

查询第一个数 == d[1] % 2 = 1 % 2 =1;

查询第二个数 == d[2] % 2 = (1+0) % 2 =1;

查询第三个数 == d[3] % 2 = (1+0+0) % 2 =1;

查询第四个数 == d[4] % 2 = (1+0+0+1) % 2 =0;

查询第五个数 == d[5] % 2 = (1+0+0+1+0) % 2 =0;

只需要用树状数组维护区间前缀和（即是单点查询）即可。

[P4588 TJOI2018]数学计算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思维+线段树维护区间乘

以时间为轴，建立线段树，叶子结点维护该操作时间的乘数，非叶子结点维护区间乘，叶子结点一开始都为1

然后每次乘，进行单点修改，将该次操作时间的位置修改为该乘数，最后输出tr[1]

每次除的话，就将询问的操作位置的乘数改为1。最后输出tr[1]

然后这题就做完了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 60;
int T, q, m;

struct node{
    int l, r;
    ll ans;
}tr[MAXN * 4];

void pushup(int u)
{
    tr[u].ans = tr[u << 1].ans * tr[u << 1 | 1].ans % m;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 1};
    if(l == r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void change(int u, int l, int r, int cnt, int val)
{
    if(tr[u].l == tr[u].r)
    {
        tr[u].ans = val;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(cnt <= mid) change(u << 1, l, r, cnt, val);
    else change(u << 1 | 1, l, r, cnt, val);
    pushup(u);
}

int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &q, &m);
        build(1, 1, q);
        for(int i = 1; i <= q; i++)
        {
            int op, x;
            scanf("%d%d", &op, &x);
            if(op == 1) {
                change(1, 1, q, i, x);
                printf("%lld\n", tr[1].ans);
            }
            else {
                change(1, 1, q, x, 1);
                printf("%lld\n", tr[1].ans);
            }
        }
    }
    return 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

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树状数组维护

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 50;
int a[MAXN], tr[MAXN], b[MAXN];
int n;

struct node{
    int val, id;
    bool operator<(const node &a)
    {
        if(val == a.val) return id < a.id;
        return val < a.val;
    }
}N[MAXN];

int lowbit(int x)
{
    return x & (-x);
}

void add(int x, int p)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += p;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
    {
        res += tr[i];
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        N[i] = {a[i], i};
    }
    sort(N + 1, N + n + 1);
    for(int i = 1; i <= n; i++) b[N[i].id] = i;
    ll sum = 0;
    for(int i = 1; i <= n; i++)
    {
        add(N[i].id, 1);
        sum += (ll)(i - query(N[i].id));
    }
    printf("%lld\n", sum);
    return 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

线段树进阶

CF242E XOR on Segment - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

线段树拆分

简单概述一下就是维护一个整数序列的区间和，支持区间异或一个数的操作。

可以把按位异或看做每个二进制位的不进制加法，也就是说你一个二进制位的结果不会影响到其他二进制位的结果。所以这个结论成立。

因为整数序列里的数最大是 1 0 6 10^6 106 , 而$ 2^{20}=1048576$ 所以这道题可以把这一个整数序列按照二进制位拆分成 20个01串，把这 20 个01串按照的方式，开 20 个线段树进行维护。

因为每个二进制位互不干扰，所以我们开20个线段树分别维护每个二进制位不影响答案的正确性。

这样这道题就瞬间简单多了，注意空间大小，不要开得过多。

#include<iostream>
#include<cstdio>
#define ll int
#define re register
using namespace std;
struct node{
	ll l,r,tag;
	long long sum;
}tree[400010][22];
ll n,m,maxk,maxx,a[100001];
long long ans,ans2;
inline ll read()
{
	re ll r=0,w=1;
	re char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		r=(r<<3)+(r<<1)+(ch^48);
		ch=getchar();
	}
	return r*w;
}
inline void pushup(ll x,ll k){tree[x][k].sum=tree[x<<1][k].sum+tree[x<<1|1][k].sum;}
inline void pushdown(ll x,ll k)
{
	if(tree[x][k].tag){
		re ll p=tree[x][k].tag;
		tree[x][k].tag=0;
		tree[x<<1][k].tag+=p;
		tree[x<<1|1][k].tag+=p;
		if(p&1){
			tree[x<<1][k].sum=(tree[x<<1][k].r-tree[x<<1][k].l+1)-tree[x<<1][k].sum;
			tree[x<<1|1][k].sum=(tree[x<<1|1][k].r-tree[x<<1|1][k].l+1)-tree[x<<1|1][k].sum;
		}
	}
}
void build(ll x,ll l,ll r)
{
	for(int k=1;k<=21;k++)
		tree[x][k].l=l,tree[x][k].r=r;
	if(l==r)
	{
		for(int k=1;k<=21;k++)
			if(a[l]&(1<<(k-1)))
				tree[x][k].sum=1;
		return ;
	}
	re ll mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	for(int k=1;k<=21;k++)
		tree[x][k].sum=tree[x<<1][k].sum+tree[x<<1|1][k].sum;
}
void qurey(ll x,ll k,ll l,ll r)
{
	if(tree[x][k].l>=l&&tree[x][k].r<=r)
	{
		ans+=tree[x][k].sum<<(k-1);
		return ;
	}
	re ll mid=tree[x][k].l+tree[x][k].r>>1;
	pushdown(x,k);
	if(mid>=l) qurey(x<<1,k,l,r);
	if(mid<r) qurey(x<<1|1,k,l,r);
	pushup(x,k);
}
void change(ll x,ll k,ll l,ll r)
{
	if(tree[x][k].l>=l&&tree[x][k].r<=r)
	{
		tree[x][k].sum=(tree[x][k].r-tree[x][k].l+1)-tree[x][k].sum;
		tree[x][k].tag++;
		return ;
	}
	re ll mid=tree[x][k].l+tree[x][k].r>>1;
	pushdown(x,k);
	if(mid>=l) change(x<<1,k,l,r);
	if(mid<r) change(x<<1|1,k,l,r);
	pushup(x,k);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,1,n);
	m=read();
	ll opt,l,r,inx,k;
	for(int i=1;i<=m;i++)
	{
		opt=read();l=read();r=read();
		if(opt==1){
			ans=0;
			for(int k=1;k<=21;k++)
			{
				ans2=0;
				qurey(1,k,l,r);
				ans+=ans2;
			}
			printf("%lld\n",ans);
		}
		else{
			inx=read();
			for(int k=1;1<<(k-1)<=inx;k++)
				if(inx&(1<<(k-1)))
					change(1,k,l,r);
		}
	}
	return 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
  • 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

[P6492 COCI2010-2011#6] STEP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

有 q 次修改，每次给定一个 x，若 a x a_x ax​ 为 L，则将 a x a_x ax​ 修改成 R，否则将 $a_x $修改成 L。

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

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

对于每一个区间，我们需要维护这个区间的

  1. 左端点值
  2. 右端点值
  3. 左边开始的最大长度
  4. 右边开始的最大长度
  5. 区间长度
  6. 区间最长的符合要求的s串

这道题的难点在于pushup函数该怎么写。我们可以先按部就班地更新一下，然后再根据我们合并的两个区间相连接处的值来进行进一步地判定。 更加准确的说，就是如果相连处的值相等就没有后续了，如果不相等就可以继续更新，更新的细节在代码里面可以自己看一下

#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
struct node{
	int lv,rv,lenl,lenr,sum,len;
}t[maxn<<2];
int n,m;
void pushup(int pos){
	t[pos].lv=t[pos<<1].lv;
	t[pos].rv=t[pos<<1|1].rv;
	t[pos].lenl=t[pos<<1].lenl;
	t[pos].lenr=t[pos<<1|1].lenr;
	t[pos].sum=max(t[pos<<1].sum,t[pos<<1|1].sum);
	if(t[pos<<1].rv!=t[pos<<1|1].lv){
		t[pos].sum=max(t[pos].sum,t[pos<<1].lenr+t[pos<<1|1].lenl);
		if(t[pos<<1].sum==t[pos<<1].len){
			t[pos].lenl=t[pos<<1].sum+t[pos<<1|1].lenl;
		}
		if(t[pos<<1|1].sum==t[pos<<1|1].len){
			t[pos].lenr=t[pos<<1|1].sum+t[pos<<1].lenr;
		}
	}
}
void build(int l,int r,int pos){
	t[pos].len=(r-l+1);
	if(l==r){
		t[pos].lv=t[pos].rv=1;
		t[pos].lenl=t[pos].lenr=1;
		t[pos].sum=1;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,pos<<1);
	build(mid+1,r,pos<<1|1);
	pushup(pos);
}
void change(int x,int l,int r,int pos){
	if(l==r){
		t[pos].lv^=1;
		t[pos].rv=t[pos].lv;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid) change(x,l,mid,pos<<1);
	if(x>mid) change(x,mid+1,r,pos<<1|1);
	pushup(pos);
}
int main(void){
	scanf("%d %d",&n,&m);
	build(1,n,1);
	int x;
	while(m--){
		scanf("%d",&x);
		change(x,1,n,1);
		printf("%d\n",max(t[1].sum,max(t[1].lenl,t[1].lenr)));
	}
}

  • 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

CF438D The Child and Sequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

区间取模，单点修改，区间求和。

观察操作，其中的取模我们是没有见到过的，显然是一个不好处理的操作，因为它不方便打标记，更很难合并标记。一般遇到这种情况，我们可以考虑暴力修改，然后再优化这个暴力的过程。

如果是区间开方，那么我们开个 7 , 8 7,8 7,8 次就能开到底，但是如果是取模呢？我们可以用一个结论： x m o d    p < x 2 x \mod p<\frac{x}{2} xmodp<2x​（证明略），所以取模也最多是$ \log x$ 次，我们不妨记录区间最大值，如果最大值 < p <p <p 直接返回，就可以通过此题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
ll a[MAXN];
int n, m;
struct Tr{
    int l, r;
    ll sum, mx;
}tr[MAXN * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)
    {
        tr[u].sum = tr[u].mx = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll ans = 0;
    if(l <= mid) ans += query(u << 1, l, r);
    if(r > mid) ans += query(u << 1 | 1, l, r);
    return ans;
}

void change(int u, int k, int x)
{
    if(tr[u].l == k && tr[u].r == k)
    {
        tr[u].mx = x;
        tr[u].sum = x;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(k <= mid) change(u << 1, k, x);
    if(k > mid) change(u << 1 | 1, k, x);
    pushup(u);
}

void mod(int u, int l, int r, int x)
{
    if(tr[u].mx < x) return;
    if(tr[u].l == tr[u].r && l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].mx = tr[u].mx % x;
        tr[u].sum = tr[u].sum % x;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) mod(u << 1, l, r, x);
    if(r > mid) mod(u << 1 | 1, l, r, x);
    pushup(u);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    // for(int i = 1; i <= 4 * n; i++) printf("l = %d r = %d sum = %lld mx = %lld\n", tr[i].l, tr[i].r, tr[i].sum, tr[i].mx);
    while(m -- )
    {
        int l, r, x, op;
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d", &l, &r);
            ll ans = query(1, l, r);
            printf("%lld\n", ans);
        }
        else if(op == 2)
        {
            scanf("%d%d%d", &l, &r, &x);
            mod(1, l, r, x);
        }
        else
        {
            scanf("%d%d", &l, &x);
            change(1, l, x);
        }
    }
    return 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
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105

★CF240F TorCoder - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

拆位线段树

题意：给定一个长为n的由a到z组成的字符串,有m次操作，每次操作将[ l , r l,r l,r]这些位置的字符进行重排，得到字典序最小的回文字符串，如果无法操作就不进行。

首先可以意识到， 每次是需要重排一整个区间的（即区间推平 / 赋值操作），我们想到线段树。

再回头，我们如何判断区间$ [l,\ r]$ 形成串 Z 能重排成一个回文串？

十分容易，我们只需按如下分类讨论即可：

  • 若 |Z| 为偶数，则 Z 内各种字母的出现次数均为偶数；
  • 若 |Z| 为奇数，则 Z 内有且仅有一种字母出现次数为奇数。

解决完这个问题，我们来到下一个问题：如何排成回文串？

这个简单，因为回文串是对称的，我们只需在 |Z| 为奇数的时候把多出的那一个放进$ [l,\ r]$ 的中间部分后，其他相同的两两一组放到未填充的边界（最左和最右）即可形成回文串。

此时我们还剩一个问题：如何使字典序最小？

把最小的字母先放前面不就好了。

到这里我们总结一下上面的步骤：

  1. 查询区间内各种字母的个数，判断是否能排； O ( n ) O(n) O(n)
  2. 若 |Z| 为奇数，则先将多出的一个放入 Z 的中间； O ( 1 ) O(1) O(1)
  3. 将字母从小到大对称放置。 O ( n ) O(n) O(n)

这整波操作是 O ( m n ) O(mn) O(mn)的，直接爆炸。

回到我们开始的线段树，发现操作 1 的个数统计，线段树可以加速成 O ( l o g 2 n ) O(log_2n) O(log2​n)。

同理，操作 2 , 3 2,3 2,3 都是区间赋值操作，同样可以拿线段树维护。

这题我懒不想打一颗线段树，就拿了空间换。反正卡不掉

那么时间就降至了 O ( m l o g 2 n ) O(mlog_2n) O(mlog2​n) 。至此，本题得到完美解决。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int maxn = 100000 + 10;
 
char s[maxn];
 
int cnt[30], n, q;
 
struct node{
    int l, r;
    int setv;
    int sum[26];
}nod[maxn<<2];
 
void pushup(int o){
    for (int i = 0; i < 26; ++i){
        nod[o].sum[i] = nod[o<<1].sum[i] + nod[o<<1|1].sum[i];
    }
}
 
 
 
void build(int l,int r,int o){
    nod[o].l = l;
    nod[o].r = r;
    nod[o].setv = -1;
    if (l == r){
        int id = s[l] - 'a';
        nod[o].sum[id] = 1;
        return;
    }
    int m = l + r >> 1;
    build(l, m, o<<1);
    build(m+1, r, o<<1|1);
    pushup(o);
}
 
void pushdown(int o){
    if (nod[o].setv != -1){
 
        int l = nod[o].l;
        int r = nod[o].r;
        int m = l + r >> 1;
        int lson = o << 1;
        int rson = o << 1 | 1;
        nod[lson].setv = nod[rson].setv = nod[o].setv;
        memset(nod[lson].sum, 0, sizeof nod[lson].sum);
        memset(nod[rson].sum, 0, sizeof nod[rson].sum);
        nod[lson].sum[nod[o].setv ] = m - l + 1;
        nod[rson].sum[nod[o].setv ] = r - m;
        nod[o].setv = -1;
    }
}
 
void update(int L,int R,int c,int l,int r,int o){
    if (L > R) return;
    if (L <= l && r <= R){
        nod[o].setv = c;
        memset(nod[o].sum,0,sizeof nod[o].sum);
        nod[o].sum[c] = r-l+1;
        return;
    }
    pushdown(o);
    int m = l + r >> 1;
    if (m >= L){
        update(L, R, c, l, m, o<<1);
    }
    if (m < R){
        update(L, R, c, m+1, r, o<<1|1);
    }
    pushup(o);
}
 
void query(int L,int R,int l,int r,int o){
    if (L > R) return;
    if (L <= l && r <= R){
        for (int i = 0; i < 26; ++i){
            cnt[i] += nod[o].sum[i];
        }
        return;
    }
    pushdown(o);
    int m = l + r >> 1;
    if (m >= L){
        query(L, R, l, m, o<<1);
    }
    if (m < R){
        query(L, R, m+1, r, o<<1|1);
    }
}
 
 
void solve(int x,int y){
    if (x > y)return;
    memset(cnt,0,sizeof cnt);
    query(x, y, 1, n, 1);
    int odd = 0;
    int pos;
    for (int i = 0; i < 26; ++i){
 
        if (cnt[i] & 1) {
            ++odd;
            pos = i;
        }
    }
    int len = y - x + 1;
    if (len & 1){
        if (odd != 1) return;
        int cur = 1;
        for (int i = 0; i < 26; ++i){
            if (!cnt[i]) continue;
 
            update(x + cur - 1, x + cur - 1 + cnt[i] / 2 - 1, i, 1, n, 1);
            update(y - cur + 1 - cnt[i] / 2 + 1, y - cur + 1, i, 1, n, 1);
            cur += cnt[i] / 2;
        }
        update(x + cur - 1, x + cur - 1, pos, 1, n, 1);
    }
    else {
        if (odd) return;
        int cur = 1;
        for (int i = 0; i < 26; ++i){
            if (!cnt[i]) continue;
            update(x + cur - 1, x + cur - 1 + cnt[i] / 2 - 1, i, 1, n, 1);
            update(y - cur + 1 - cnt[i] / 2 + 1, y - cur + 1, i, 1, n, 1);
            cur += cnt[i] / 2;
        }
    }
}
 
 
void dfs(int l,int r,int o){
    if (l == r){
        for (int i = 0; i < 26; ++i){
            if (nod[o].sum[i]){
                printf("%c", i + 'a');
                break;
            }
        }
        return;
    }
    if (nod[o].setv != -1){
        for (int i = l; i <= r; ++i){
            printf("%c", nod[o].setv + 'a');
        }
        return;
    }
 
    int m = l + r >> 1;
    dfs(l, m ,o<<1);
    dfs(m+1,r,o<<1|1);
}
 
/**
7 1
aabcbaa
5 7
**/
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d%d",&n, &q);
    scanf("%s", s + 1);
    build(1, n, 1);
    while(q--){
        int x,y;
        scanf("%d%d",&x, &y);
        solve(x,y);
    }
 
    dfs(1, n, 1);
    putchar('\n');
    return 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
  • 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

CF431E Chemistry Experiment - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

动态开点+权值线段树

操作一直接跳过，单点修改太逊了。

看操作二：这玩意什么鬼？

仔细分析一下，一个结论明显得出：

  • 最后有水的试管水面高度都是相同的。

这个显然，因为题目要求最高的水平水面尽量矮，所以若有水面高度差，我们直接拿高的往低的里面灌就能减小答案。

同时，我们发现，答案具有单调性。也就是说，我们如果强制所有水面到达 x 高度这个方案可行，那么所有 ≥ x \ge x ≥x 的方案均可。

果断二分答案。

二分 mid 之后，思考如何判断这个答案可不可行。

因为只能往小于等于 mid 的试管里面灌，也就是说我们要统计出所有高度小于等于 mid的试管的数量 num，同时也要统计这些试管里面水银的体积 sum。如果 n u m × m i d − s u m ≥ v num \times mid - sum \ge v num×mid−sum≥v这个 mid就是可行的（自行画图体会）。

又由于没有区间限制，而且 mid 值不确定，果断上权值线段树 + 动态开点。

时间复杂度 O ( m l o g 2 S ) O(mlog^2S) O(mlog2S)。不是很需要卡常。

注意动态开点不要使用 vector，内存尽量卡大一点即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50, inf = 1e9;
int n, m, tot, rt;
int a[MAXN];
struct Tr{
    int ls, rs;
    ll sum, cnt;
}tr[MAXN * 50];

void pushup(int u)
{
    tr[u].sum = (tr[tr[u].ls].sum + tr[tr[u].rs].sum);
    tr[u].cnt = (tr[tr[u].ls].cnt + tr[tr[u].rs].cnt);
}

void change(int &cur, int l, int r, ll x, ll sum, ll cnt)
{
    if(!cur) cur = ++tot;
    if(l == r)
    {
        tr[cur].sum += sum;
        tr[cur].cnt += cnt;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) change(tr[cur].ls, l, mid, x, sum, cnt); // 这部分与普通线段树不同，需要判断按照数值大小进行插入
    else change(tr[cur].rs, mid + 1, r, x, sum, cnt);
    pushup(cur);
}

ll query(int u, int l, int r, double cl, double cr, int flag) // cl和cr，l和r注意区分
{
    if(!u) return 0;
    if(r == inf && cr > r) cr = inf;
    if(cl <= l && r <= cr)
    {
         if(flag == 1) return tr[u].sum;
         else return tr[u].cnt;
    }
    int mid = (l + r) >> 1;
    ll res = 0;
    if(cl <= mid) res += query(tr[u].ls, l, mid, cl, cr, flag);
    if(cr > mid) res += query(tr[u].rs, mid + 1, r, cl, cr, flag);
    return res;
}

double solve(ll x)
{
    double l = 0, r = 1e15, ans = 0;
    while(r - l >= 1e-4)
    {
        double mid = (l + r) / 2.0;
        if(query(rt, 0, inf, 0, mid, 1) + x <= query(rt, 0, inf, 0, mid, 0) * mid) {ans = mid, r = mid;}
        else l = mid;
    }
    return ans;
}


int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        change(rt, 0, inf, a[i], a[i], 1);
    }
    while(m --)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            change(rt, 0, inf, a[x], -a[x], -1); // 动态开点的时候注意更新，修改前的值清空，修改后的值加一。
            a[x] = y;
            change(rt, 0, inf, y, y, 1);
        }
        else {
            ll v;
            scanf("%lld", &v);
            double ans = solve(v);
            printf("%.4f\n", ans);
        }
    }
    return 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
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93

P2184 贪婪大陆 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

树状数组的模板题

1.只要一个区间的开头在一个节点 i i i的左边，那么这个区间包含在区间1~i中。

2.只要一个区间的尾部在一个节点 j j j的左边，那么这个区间肯定不属于j后的所有区间

所以我们可以搞两个树状数组来做

t r e e h e a d [ i ] tree_{head}[i] treehead​[i]维护 i i i之前的开头数量

t r e e t a i l [ j ] tree_{tail}[j] treetail​[j]维护 j j j前的结尾数量

结合样例可以看出来 t r e e h e a d [ j ] − t r e e t a i l [ i ] tree_{head}[j]-tree_{tail}[i] treehead​[j]−treetail​[i]即为 i − j i-j i−j之间的雷种类数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 50;
int trhead[MAXN], trtail[MAXN];
int n, m;

int lowbit(int x)
{
    return x & (-x);
}

void changehead(int x, int p)
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        trhead[i] += p;
    }
}

void changetail(int x, int p)
{
    for(int i = x; i <= n; i+= lowbit(i))
    {
        trtail[i] += p;
    }
}

int getsumhead(int x)
{
    int res = 0;
    for(int i = x; i ; i -= lowbit(i))
    {
        res += trhead[i];
    }
    return res;
}

int getsumtail(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
    {
        res += trtail[i];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if(op == 1)
        {
            changehead(l, 1);
            changetail(r, 1);
        }
        else
        {
            int ans = getsumhead(r) - getsumtail(l- 1);
            printf("%d\n", ans);
        }
    }
    return 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

P1438 无聊的数列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对差分数组建线段树

维护区间和区间修改

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 500;
int n, m;
int a[MAXN], cf[MAXN];

struct Tr{
    int l, r;
    ll lazy, sum;
}tr[MAXN * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    ll lazy = tr[u].lazy;
    if(lazy)
    {
        tr[u << 1].lazy += lazy;
        tr[u << 1 | 1].lazy += lazy;
        tr[u << 1].sum += (ll)(tr[u << 1].r - tr[u << 1].l + 1) * lazy;
        tr[u << 1 | 1].sum += (ll)(tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * lazy;
        tr[u].lazy = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)
    {
        tr[u].sum = cf[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void change(int u, int l, int r, int k)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].lazy += k;
        tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * k;
        return;
    }
    pushdown(u); // 记住都要pushdown
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) change(u << 1, l, r, k);
    if(r > mid) change(u << 1 | 1, l, r, k);
    pushup(u);
}

ll query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll res = 0;
    if(l <= mid) res += query(u << 1, l, r);
    if(r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        cf[i] = a[i] - a[i - 1];
    }
    build(1, 1, n);
    while(m --)
    {
        int op, l, r, k, d;
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d%d%d", &l, &r, &k, &d);
            change(1, l, l, k);
            if(r > l) change(1, l + 1, r, d);	// 注意判断条件
            if(r < n) change(1, r + 1, r + 1, - k - (r - l) * d); // 注意条件
        }
        else
        {
            scanf("%d", &l);
            ll ans = query(1, 1, l);
            printf("%lld\n", ans);
        }
    }
    return 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
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106

CF992E Nastya and King-Shamans - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给定一个序列$ a_i$ ，记其前缀和序列为 s i s_i si​ ，有 q 个询问，每次单点修改，询问是否存在一个 i 满足 a i = s i − 1 a_i=s_{i-1} ai​=si−1​ ，有多解输出任意一个，无解输出 -1 。

每次从p=1 跳起 每次跳到 sum[i]>=2*sum[p]的最小的i处

可以证明答案一定在跳过的i上（反证法）

理性的想一下，如果sum[i]<2*sum[p]

那么sum[i]-sum[p]<sum[p]

由于i>p所以一定不存在num[i]=sum[i-1]

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
inline void write(int x){if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0');}
inline void writeln(int x){write(x); puts("");}
const int N=2e5+5;
typedef long long ll;
int n,num[N],q;
ll sum[N],S;
inline void init(){
	n=read(); q=read();
	for (int i=1;i<=n;i++) num[i]=read(); 
}
struct node{
	ll mx,plu;
}a[N<<2];
void build(int k,int l,int r){
	a[k].mx=sum[r];
	if (l==r) return;
	int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r);
}
inline void plus(int k,ll w){
	a[k].mx+=w; a[k].plu+=w;
}
inline void pushdown(int k){
	if (a[k].plu){
		plus(k<<1,a[k].plu);
		plus(k<<1|1,a[k].plu);
		a[k].plu=0;
	}
}
inline void pushup(int k){
	a[k].mx=max(a[k<<1].mx,a[k<<1|1].mx);
}
void upd(int k,int l,int r,int x,int y,int w){
	if (l==x&&r==y) {plus(k,w); return;}
	int mid=(l+r)>>1; pushdown(k);
	if (mid>=y) upd(k<<1,l,mid,x,y,w);
		else if (mid<x) upd(k<<1|1,mid+1,r,x,y,w);
			else upd(k<<1,l,mid,x,mid,w),upd(k<<1|1,mid+1,r,mid+1,y,w);
	pushup(k);
}
int qry(int k,int l,int r,ll x){
	if (a[k].mx<2ll*x) return 0;
	if (l==r) {S=a[k].mx; return r;}
	int mid=(l+r)>>1; pushdown(k);
	if (a[k<<1].mx>=2ll*x) return qry(k<<1,l,mid,x);
		else return qry(k<<1|1,mid+1,r,x);
}
inline void solve(){
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+num[i];
	build(1,1,n);
	for (int i=1;i<=q;i++){
		int x=read(),w=read();
		upd(1,1,n,x,n,w-num[x]);
		num[x]=w; S=num[1];
		if (S==0){
			puts("1");
			continue;
		}
		for (;;){
			int p=qry(1,1,n,S);
			if (!p) {
				puts("-1");
				break;
			}else{
				if (S==2ll*num[p]) {
					writeln(p);
					break;
				}
			}
		}
	}
}
int main(){
	init();
	solve();
	return 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

CF1000F One Occurrence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给定一个长度为n序列，m个询问，每次询问给定一个区间 [ l , r ] [l,r] [l,r]，如果这个区间里存在只出现一次的数，输出这个数（如果有多个就输出任意一个），没有就输出0， n , m < = 5 ∗ 1 0 5 n,m<=5∗10^5 n,m<=5∗105

我们有一个询问区间$ [l,r]$，题目要求你找出其中只出现了一次的数。

我们单独考虑某个数 x，假设其在 [ l , r ] [l,r] [l,r]中出现的下标最大的位置为 p。

那么，x 在区间 [ l , r ] [l,r] [l,r] 只出现了一次等价于 p 存在并且相对于 p，x 上一次出现的位置 <l。

一棵线段树就行了，从左往右依次把每个位置的数字pre的位置加上，线段树的节点表示位置
考虑以i为右节点，左节点为l（很多个）的情况。
我们线段树维护每个节点的pre的min，如果min < l，说明这个数字在l~r中只出现了一次，就是个合法的数字，那么我们区间查询合法数字就行

可以在每一个位置 i 维护 a i a_i ai​ 上一次出现的位置。在查询 [ l , r ] [l,r] [l,r] 的时候如果该区间上的最小值 <l，则一定有数只出现了一次。用线段树维护，同时记录一下最小值对应的数是什么即可。

为了保证在最靠右的 x 处记录信息，我们需要将询问按照右端点排序，离线处理。

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
const int N=500005;
int ans[N],a[N],pre[N],last[N];
struct hh{int pre,x;hh(int X=0,int Y=0){pre=X; x=Y;}}tree[N*4],hx;
vector<hh>q[N];
bool operator <(hh a,hh b){return a.pre<b.pre;}
void updata(int now){tree[now]=min(tree[now<<1],tree[now<<1|1]);}
void change(int now,int l,int r,int x)
{
    if (l==r){tree[now]=hx;return;}
    int mid=(l+r)>>1;
    if (x<=mid) change(now<<1,l,mid,x);
    else change(now<<1|1,mid+1,r,x); 
    updata(now);
}
void qurry(int now,int l,int r,int lrange,int rrange)
{
    if (lrange<=l && rrange>=r) {hx=min(hx,tree[now]);return;}
    int mid=(l+r)>>1;
    if (lrange<=mid) qurry(now<<1,l,mid,lrange,rrange);
    if (rrange>mid) qurry(now<<1|1,mid+1,r,lrange,rrange);
}
int main()
{
    int n,Q;scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&Q);
    for (int i=1;i<=Q;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        q[y].push_back((hh){x,i});
    }
    for (int i=1;i<=n;i++)
    {
        pre[i]=last[a[i]];
        last[a[i]]=i;
    }
    for (int i=1;i<=n;i++)
    {
        if (pre[i])
          {hx=hh(INF,INF);change(1,1,n,pre[i]);}
        hx=hh(pre[i],a[i]);
        change(1,1,n,i);
        for (int j=0;j<q[i].size();j++)
        {
            hx=hh(INF,INF);
            qurry(1,1,n,q[i][j].pre,i);
            if (hx.pre<q[i][j].pre) ans[q[i][j].x]=hx.x;
            else ans[q[i][j].x]=0;
        }
    }
    for (int i=1;i<=Q;i++) printf("%d\n",ans[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

CF1149C Tree Generator™ - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：n个点，m个询问。

给你一棵树的括号序列，输出它的直径。

有m次询问，每次询问表示交换两个括号，输出交换两个括号后的直径（保证每次操作后都为一棵树）

如何使用树构建括号序列。

Dfs，每经过一条边，往下走就加入“(”，往上走就加入“)”。

引理1.1 若从序列中任取一段连续子序列，从中去掉所有匹配括号后，剩下的括号组成的路径一定为一条链，链长为剩下的子序列长。

引理1.2 树上直径长度即为任意区间去掉匹配括号后的长度的最大值。

若我们给”(”赋值 +1，给”)”赋值 -1，则：

引理1.3 最长匹配区间 = 最大的（将区间分成两段）后面的权值和 - 前面的权值和

维护相邻区间差最大值

需要维护区间和，区间答案，区间右减左，前/后缀（最大值，最小值，右减左）

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=2e5+5;
int n,m;
char s[N];
int sum[N<<2],lma[N<<2],lmi[N<<2],rma[N<<2],rmi[N<<2],ld[N<<2],rd[N<<2],mad[N<<2],tr[N<<2];
//sum区间和，lma前缀大，lmi前缀小，rma后缀大，rmi后缀小，ld前缀右减左，rd后缀右减左，mad区间右减左，tr区间答案 

int max(int x,int y){
	return x>y?x:y;
}

int min(int x,int y){
	return x<y?x:y;
}

void pushup(int x){
	sum[x]=sum[x<<1]+sum[x<<1|1]; //直接加
	lma[x]=max(lma[x<<1],sum[x<<1]+lma[x<<1|1]); //经典分两类取最值
	rma[x]=max(rma[x<<1|1],sum[x<<1|1]+rma[x<<1]);
	lmi[x]=min(lmi[x<<1],sum[x<<1]+lmi[x<<1|1]);
	rmi[x]=min(rmi[x<<1|1],sum[x<<1|1]+rmi[x<<1]);
	ld[x]=max(ld[x<<1],max(ld[x<<1|1]-sum[x<<1],mad[x<<1]+lma[x<<1|1])); //类似上面的最大最小子段和
	rd[x]=max(rd[x<<1|1],max(sum[x<<1|1]+rd[x<<1],mad[x<<1|1]-rmi[x<<1]));
	mad[x]=max(mad[x<<1]+sum[x<<1|1],mad[x<<1|1]-sum[x<<1]);
	tr[x]=max(max(tr[x<<1],tr[x<<1|1]),max(ld[x<<1|1]-rmi[x<<1],rd[x<<1]+lma[x<<1|1])); //该区间答案的答案有四种情况，同样取个max
}

void build(int x,int l,int r){
	if(l==r){
		int v=s[l]=='('?1:-1;
		sum[x]=v; //赋初值
		lma[x]=rma[x]=max(v,0);
		lmi[x]=rmi[x]=min(v,0);
		ld[x]=rd[x]=mad[x]=tr[x]=1; //初始肯定是一个多余的括号
		return ;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}

void up(int x,int l,int r,int p,int v){
	if(l==r){
		sum[x]=v;
		lma[x]=rma[x]=max(v,0);
		lmi[x]=rmi[x]=min(v,0);
		ld[x]=rd[x]=mad[x]=tr[x]=1;
		return ;
	}
	int mid=l+r>>1;
	if(p<=mid) up(x<<1,l,mid,p,v);
	else up(x<<1|1,mid+1,r,p,v);
	pushup(x);
}

signed main(){
	read(n);read(m);scanf("%s",s+1);
	n=n-1<<1; //括号序列的长度
	build(1,1,n);
	write(tr[1]);puts("");
	while(m--){
		int x,y;
		read(x);read(y);
		if(s[x]!=s[y]){ //小优化，相同就不用做了（但其实期望1/2的操作都能被跳过）
			swap(s[x],s[y]);
			up(1,1,n,x,s[x]=='('?1:-1); //单点修改
			up(1,1,n,y,s[y]=='('?1:-1);
		}
		write(tr[1]);puts("");
	}
}

  • 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

CF1422F Boring Queries - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一个比较套路的做法，强制在线算法应该先考虑离线做法。

我们对询问离线，按区间右端点排序。

对于区间右端点固定，当左端点向左移动时，每次会增加一个数。当且仅当增加的数存在一个因子 p w p^w pw，原来的 l c m \rm lcm lcm的 p p p的指数小于 w w w时，答案会增大。更具体一点，原来 l c m \rm lcm lcm的p的指数会对w取 max ⁡ \max max。

这样对于两个数 a i , a j ( i < j ) a_i,a_j(i<j) ai​,aj​(i<j)，质因子p对应的指数分别为x,y，若x<y，则 a i a_i ai​一定不会更新答案。这样的 a i a_i ai​可以直接丢掉。

我们发现这非常类似单调栈的过程。但是我们还有区间左端点的限制，这可以用线段树维护一下。

回到原题，我们要强制在线，一个比较套路的做法是直接上可持久化线段树，然后这道题就做完了。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/180067
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号