精华内容
下载资源
问答
  • 势能线段树(吉司机线段树)专题 势能线段树在近期训练时遇到了好几次,但是由于本人太懒一直没补完,结果ICPC网络赛还真就出了一道势能线段树Orz……结果当然是没做出来……痛定思痛,这回把之前欠的一块儿补了。 ...

    势能线段树(吉司机线段树)专题

    势能线段树在近期训练时遇到了好几次,但是由于本人太懒一直没补完,结果ICPC网络赛还真就出了一道势能线段树Orz……结果当然是没做出来……痛定思痛,这回把之前欠的一块儿补了。

    简要介绍

    ​ 我们知道,传统的支持区间修改的线段树是通过lazy标记来规避掉频繁大规模的单点修改来实现对时间开销的节省的。那么对于一种区间操作,其能使用lazy标记需要满足两个条件:

    1. 区间节点的值可以通过对当前结点lazy标记的计算来更新
    2. 多次不同的lazy标记可以实现就地的快速合并

    ​ 比如经典的区间加和区间乘修改,区间求和查询,当前结点的值可以通过加上lazy乘区间长度和乘上lazy的值来进行轻易的修改,lazy标记的值也可以通过简单的相加或相乘来更新。

    ​ 但是对于像区间开根号、区间位运算这样的区间操作来说,其对每个结点的修改量是在一定程度上是由叶结点本身现有的值来决定的,那么就很难实现lazy的合并和对区间值的直接更新,好像只有对所有叶结点进行单点修改这一种办法,而这种方法在时间开销上是绝对不允许的。

    ​ 但是再仔细观察这其中的某些操作,区间开根号,每个点顶多被开log次,当结点的值被开到1时,以后的操作就都不会对结点的值产生影响了。区间与值运算也是同理,与运算不会使结点值中二进制1的个数增加,而当结点的值变为0时,与值操作也就不能对值产生影响了。我们发现这些操作对每个结点的操作次数都是有一个隐含的“上限”的,就像有一个固定的“势能“,只要超过了这个上限值,相应的操作便会“退化”失效,也就是势能为0的情况。而当势能为0的结点连成区间时,我们便可以一口气规避掉在这个区间上的所有操作。而一般这种势能的下降还是非常迅速的,这也是势能线段树节省时间的原因。

    ​ 所以,我们可以这样构建和操作这个线段树:

    1. 在每个线段树结点加入一个”势能函数“,来记录和维护当前区间结点的势能情况。
    2. 对于每次的区间修改,若当前区间内所有结点的势能皆已为零,直接退出递归不再修改
    3. 若当前区间内还存在势能不为零的结点,则继续向下递归,暴力修改要求区间内每一个势能不为零的结点

    ​ 至于具体的时间复杂度…据说每次修改不会超过O(log2n)……具体的证明嘛……

    题目归纳

    2021CCPC 黑龙江省赛 A And RMQ (Gym - 103107A

    题目大意

    给定一组序列,定义三种操作:

    AND l r v :将从l到r的区间所有的结点和v进行与运算

    UPD x v:单点修改,将x位置的值修改为v

    QUE l r:询问区间l到r的区间最大值

    进行最大400000次操作。

    解题思路

    几乎是势能线段树的模板题,可以看出,如果在区间所与的v的值位权为0的位置上,待修改区间所有值在这些位置的位权皆为0,那么区间与值操作对于该区间就是无效的。那么可以使用或运算计算区间值位权为0的交集作为势能值的记录,每次区间操作先查询v值位权为0的位置在相应区间上是否存在1,若存在,接着向下修改,若不存在,直接退出修改。

    在这里插入图片描述

    AC代码

    #include <iostream>
    #include <fstream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <map>
    #include <set>
    #include<bitset>
    #pragma warning(disable:4996)
    #pragma GCC optimize (2)
    #pragma G++ optimize (2)
    #define inr register int
    #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define debug(a) cout << #a << " " << a << endl
    using namespace std;
    typedef long long long long;
    const double pi = acos(-1.0);
    const double eps = 1e-8;
    const int inf = 0x3f3f3f3f;
    const int 1000007 = 400007;//1e5+7 
    
    int read()
    {
    	int res = 0, ch, flag = 0;
    	if ((ch = getchar()) == '-')
    		flag = 1;
    	else if (ch >= '0' && ch <= '9')
    		res = ch - '0';
    	while ((ch = getchar()) >= '0' && ch <= '9')
    		res = res * 10 + ch - '0';
    	return flag ? -res : res;
    }
    
    
    #define lson (o<<1)
    #define rson (o<<1|1)
    
    int arr[1000007];
    
    struct node {
    	int mx;
    	int tag;
    }tree[1000007 << 2];
    
    
    inline void pushup(int o)
    {
    	tree[o].mx = max(tree[lson].mx, tree[rson].mx);
    	tree[o].tag = tree[lson].tag | tree[rson].tag;//收集区间内所有位权1,作为势能函数
    }
    
    void build(int o, int l, int r)
    {
    	if (l == r) {
    		tree[o] = { arr[l] , arr[l] };
    		return;
    	}
    	int mid = (l + r) >> 1;
    	build(lson, l, mid);
    	build(rson, mid + 1, r);
    	pushup(o);
    }
    
    void modify(int o, int l, int r, int ml, int mr, int x)
    {
    	if (!((~x) & tree[o].tag)) {
    		return;
    	}
    	if (l == r) {
    		tree[o].mx &= x;
    		tree[o].tag &= x;
    		return;
    	}
    	int mid = (l + r) >> 1;
    	if (ml <= mid) {
    		modify(lson, l, mid, ml, mr, x);
    	}
    	if (mid + 1 <= mr) {
    		modify(rson, mid + 1, r, ml, mr, x);
    	}
    	pushup(o);
    }
    
    void update(int o, int l, int r, int p, int x)
    {
    	if (l == r) {
    		tree[o] = { x,x };
    		return;
    	}
    	int mid = (l + r) >> 1;
    	if (p <= mid) {
    		update(lson, l, mid, p, x);
    	}
    	else {
    		update(rson, mid + 1, r, p, x);
    	}
    	pushup(o);
    }
    
    int query(int o, int l, int r, int ql, int qr)
    {
    	if (ql <= l && r <= qr) {
    		return tree[o].mx;
    	}
    	int mid = (l + r) >> 1, res = 0;
    	if (ql <= mid) {
    		res = max(res, query(lson, l, mid, ql, qr));
    	}
    	if (mid + 1 <= qr) {
    		res = max(res, query(rson, mid + 1, r, ql, qr));
    	}
    	return res;
    }
    
    char st[17];
    
    int main()
    {
    	int n = read(), m = read();
    	for (int i = 1; i <= n; i++) {
    		arr[i] = read();
    	}
    	build(1, 1, n);
    	int opl, opr, opx;
    	while (m--) {
    		scanf("%s%d", st, &opl);
    		if (st[0] == 'A') {
    			opr = read(); opx = read();
    			modify(1, 1, n, opl, opr, opx);
    		}
    		else if (st[0] == 'U') {
    			opx = read();
    			update(1, 1, n, opl, opx);
    		}
    		else {
    			opr = read();
    			printf("%d\n", query(1, 1, n, opl, opr));
    		}
    	}
    	return 0;
    }
    

    2021杭电中超(8)D Counting Stars (HDU 7059

    题目大意

    同样是求区间和,给定两种区间修改操作

    1. 询问区间和
    2. 区间l到r所有值加上其highbit
    3. 区间l到r所有值减去其lowbit

    解题思路

    ​ 与黑龙江省赛大同小异,可以看出对于每个值其位权1的个数是一定的,而每进行一次操作3其数量会减一,操作2不会增加其数量。于是使用cnt来记录当前区间最多的位权1数量,若cnt为0,则不需要再修改。注意将每个数的hibit和剩下值分开存储,这样操作2就变成纯粹的区间乘操作,更好维护。

    AC代码

    #include <iostream>
    #include <fstream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <map>
    #include <set>
    #pragma GCC optimize(2)
    #pragma GCC optimize("Ofast","inline","-ffast-math")
    #pragma GCC optimize(3)
    #pragma GCC optimize(3,"Ofast","inline")
    #pragma G++ optimize(2)
    #pragma G++ optimize("Ofast","inline","-ffast-math")
    #pragma G++ optimize(3)
    #pragma G++ optimize(3,"Ofast","inline")
    #pragma warning(disable:4996)
    #define inr register int
    #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define debug(a) cout << #a << " " << a << endl
    using namespace std;
    typedef long long ll;
    const double pi = acos(-1.0);
    const double eps = 1e-8;
    const int inf = 0x3f3f3f3f;
    const int maxn = 1000007;//1e5+7 
    const ll mod = 998244353;//1e9+7
    
    #define lson (o<<1)
    #define rson (o<<1|1)
    
    ll arr[maxn];
    ll m2[maxn];
    
    inline ll lowbit(ll x)
    {
        return x & (-x);
    }
    
    inline ll hbit(ll x)
    {
        for (inr i = 30; i >= 0; i--) {
            if (x >> i & 1) {
                return 1 << i;
            }
        }
    }
    
    inline void init()
    {
        m2[0] = 1;
        for (inr i = 1; i < maxn; i++) {
            m2[i] = (m2[i - 1] * 2) % mod;
        }
    }
    
    struct node {
        ll hb, lb, cnt, lazy;
    }tree[maxn << 2];
    
    inline void pushup(int o)
    {
        tree[o].lb = (tree[lson].lb + tree[rson].lb) % mod;
        tree[o].hb = (tree[lson].hb + tree[rson].hb) % mod;
        tree[o].cnt = max(tree[lson].cnt, tree[rson].cnt);
    }
    
    inline void pushdown(int o)
    {
        if (tree[o].lazy) {
            tree[lson].lazy += tree[o].lazy;
            tree[rson].lazy += tree[o].lazy;
            tree[lson].hb = (tree[lson].hb * m2[tree[o].lazy]) % mod;
            tree[rson].hb = (tree[rson].hb * m2[tree[o].lazy]) % mod;//hb??lb 
            tree[o].lazy = 0;
        }
    }
    
    inline void build(int o, int l, int r)
    {
        tree[o] = { 0,0,0,0 };//??????? 
        if (l == r) {
            tree[o].hb = hbit(arr[l]);
            tree[o].lb = arr[l] - tree[o].hb;
            tree[o].cnt = __builtin_popcount(arr[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        pushup(o);
    }
    
    inline void modify(int o, int l, int r, int ml, int mr)
    {
        if (!tree[o].cnt) {
            return;
        }
        if (l == r) {
            if (tree[o].cnt > 1) {
                tree[o].lb -= lowbit(tree[o].lb);
                tree[o].cnt--;;
            }
            else {
                tree[o].hb = tree[o].cnt = 0;
            }
            return;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        if (ml <= mid) {
            modify(lson, l, mid, ml, mr);
        }
        if (mid + 1 <= mr) {
            modify(rson, mid + 1, r, ml, mr);
        }
        pushup(o);
    }
    
    inline void update(int o, int l, int r, int ul, int ur)
    {
        if (!tree[o].cnt) {
            return;
        }
        if (ul <= l && r <= ur) {
            tree[o].hb = tree[o].hb * 2 % mod;
            tree[o].lazy += 1;
            return;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        if (ul <= mid) {
            update(lson, l, mid, ul, ur);
        }
        if (mid + 1 <= ur) {
            update(rson, mid + 1, r, ul, ur);
        }
        pushup(o);
    }
    
    inline ll query(int o, int l, int r, int ql, int qr)
    {
        if (!tree[o].cnt) {
            return 0ll;
        }
        if (ql <= l && r <= qr) {
            return tree[o].hb + tree[o].lb;
        }
        pushdown(o);
        int mid = (l + r) >> 1;
        ll res = 0;
        if (ql <= mid) {
            res = (res + query(lson, l, mid, ql, qr)) % mod;
        }
        if (mid + 1 <= qr) {//qr??r 
            res = (res + query(rson, mid + 1, r, ql, qr)) % mod;
        }
        return res;
    }
    
    int main()
    {
        int T, n, m;
        init();
        scanf("%d", &T);
        while (T--) {
            scanf("%d", &n);
            for (int i = 1; i <= n; i++) {
                scanf("%lld", arr + i);
            }
            scanf("%d", &m);
            build(1, 1, n);
            int opt, opl, opr;
            while (m--) {
                scanf("%d%d%d", &opt, &opl, &opr);
                if (opt == 1) {
                    printf("%lld\n", query(1, 1, n, opl, opr));
                }
                else if (opt == 2) {
                    modify(1, 1, n, opl, opr);
                }
                else {
                    update(1, 1, n, opl, opr);
                }
            }
    
        }
        return 0;
    }
    

    2021 ICPC 网络赛 第二场 L Euler Function

    题目大意

    给定序列,定义两种操作

    0 l r w :区间l到r的值都乘以w

    1 l r :查询区间l到r的欧拉函数值的和 mod 998244353

    注意序列初始值和w值皆不大于100

    解题思路

    注意欧拉函数的性质: 若i mod p=0,其中p为质数,则 φ ( i ∗ p ) = p ∗ φ ( i ) φ(i * p) = p * φ( i ) φ(ip)=pφ(i) 否则 φ ( i ∗ p ) = ( p − 1 ) ∗ φ ( i ) φ( i * p ) = ( p - 1) * φ( i ) φ(ip)=(p1)φ(i)

    因为x和w的值都不大于100,所以其实其都能分解为100以内的质数,根据上面描述的性质,我们将一次区间乘w的更新分解为对其质因数的分别更新,这样,如果某质数为该区间内共同的因数,则对当前区间欧拉函数的修改就变为简单的区间乘问题(直接乘p就行)。否则,继续向下递归修改。100以内的素数只有不到30个,可以使用bitset进行状态压缩处理,这样通过二进制位上的运算就可以很好的反应结点势能情况。

    AC代码

    #include <iostream>
    #include <fstream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <bitset>
    #include <map>
    #include <set>
    #pragma warning(disable:4996)
    #define inr register int
    #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define debug(a) cout << #a << " " << a << endl
    #define lson (o<<1)
    #define rson (o<<1|1)
    using namespace std;
    typedef long long ll;
    const double pi = acos(-1.0);
    const double eps = 1e-8;
    const int inf = 0x3f3f3f3f;
    const int maxn = 100007;//1e5+7
    const int maxm = 107;
    const ll mod = 998244353;//1e9+7
    
    //势能线段树的核心思想:虽然有些操作看起来不能区间修改,但是其实修改的操作是有上界的
    //即某些操作在执行了一定次数后便会退化,比如开根、取最小值等操作。
    //那么思路就是在线段树中记录这种势能的变化,当操作退化时将单点操作转为区间操作,即可大大节省时间
    
    
    int phi[maxm], prime[maxm];//前一百个数的欧拉函数,前一百中的素数
    bool del[maxm];//判断素数
    int cnt[maxm][30];
    bitset<30>st[maxm];
    
    ll ksm(ll x, ll y)
    {
    	ll ans = 1;
    	x = x % mod;
    	while (y > 0)
    	{
    		if (y & 1) ans = (ans * x) % mod;
    		y >>= 1;
    		x = (x * x) % mod;
    	}
    	return ans;
    }
    
    void euler()//欧拉筛,同时求欧拉函数
    {
    	for (int i = 2; i < maxm; i++) {
    		if (!del[i]) {
    			prime[++prime[0]] = i;
    			phi[i] = i - 1;
    		}
    		for (int j = 1; j <= prime[0] && ll(prime[j]) * i < maxm; j++) {
    			int tp = prime[j] * i;
    			del[tp] = 1;
    			if (i % prime[j] == 0) {
    				phi[tp] = phi[i] * prime[j];
    				break;
    			}
    			phi[tp] = phi[i] * (prime[j] - 1);
    		}
    	}
    	phi[1] = 1;
    }
    
    ll w[maxn];
    struct node {
    	ll sum, lazy;//求和值,区间乘lazy
    	bitset<30>tag;//可以看作一种势能的记录?
    }tree[maxn << 2];
    
    void pushup(int o)
    {
    	tree[o].sum = (tree[lson].sum + tree[rson].sum) % mod;//朴素的计算
    	tree[o].tag = tree[lson].tag & tree[rson].tag;//代表区间全部覆盖的质因数
    }
    
    void pushdown(int o)//区间乘正常操作
    {
    	tree[lson].lazy = tree[lson].lazy * tree[o].lazy % mod;
    	tree[rson].lazy = tree[rson].lazy * tree[o].lazy % mod;
    	tree[lson].sum = tree[lson].sum * tree[o].lazy % mod;
    	tree[rson].sum = tree[rson].sum * tree[o].lazy % mod;
    	tree[o].lazy = 1;
    }
    
    void build(int o, int l, int r)
    {
    	if (l == r) {
    		tree[o] = { phi[w[l]],1,st[w[l]] };//存入对应的欧拉函数、质因数状态,lazy初始化
    		return;
    	}
    	tree[o] = { 0,1 };//非叶节点的tag等待pushup
    	int mid = (l + r) >> 1;
    	build(lson, l, mid);
    	build(rson, mid + 1, r);
    	pushup(o);
    }
    
    void modify(int o, int l, int r, int ml, int mr, pair<int, int>d)//对数的修改一定是以素数的幂次进行的
    {
    	if (ml <= l && r <= mr && tree[o].tag[d.first]) {//如果当前节点在修改区间内,该素数是该区间共有的因数
    		tree[o].lazy = tree[o].lazy * ksm(prime[d.first], d.second) % mod;//那么就是区间乘,直接乘就行
    		tree[o].sum = tree[o].sum * ksm(prime[d.first], d.second) % mod;
    	}
    	else if (l == r) { //如果来到叶节点
    		if (tree[o].tag[d.first]) {//若叶节点包含该素数
    			tree[o].sum = tree[o].sum * ksm(prime[d.first], d.second) % mod;//直接乘上去
    		}
    		else {//若不包含
    			tree[o].tag[d.first] = 1;//更新tag
    			tree[o].sum = tree[o].sum * (prime[d.first] - 1) % mod;//更新欧拉函数的值(根据上面的性质)
    			tree[o].sum = tree[o].sum * ksm(prime[d.first], d.second - 1) % mod;
    		}
    	}
    	else {//若区间不全包含该素数,向下遍历更新,可知该操作的势能一定是不断减小的
    		if (tree[o].lazy != 1) {
    			pushdown(o);
    		}
    		int mid = (l + r) >> 1;
    		if (ml <= mid) {
    			modify(lson, l, mid, ml, mr, d);
    		}
    		if (mid + 1 <= mr) {
    			modify(rson, mid + 1, r, ml, mr, d);
    		}
    		pushup(o);
    	}
    }
    ll query(int o, int l, int r, int ql, int qr)
    {
    	if (ql <= l && r <= qr) {
    		return tree[o].sum;
    	}
    	pushdown(o);
    	int mid = (l + r) >> 1;
    	ll res = 0;
    	if (ql <= mid) {
    		res = (res + query(lson, l, mid, ql, qr)) % mod;
    	}
    	if (mid + 1 <= qr) {
    		res = (res + query(rson, mid + 1, r, ql, qr)) % mod;
    	}
    	return res;
    }
    
    ll ans[maxn];
    
    int main()
    {
    	ios;
    	euler();
    	for (int i = 1, x; i < maxm; i++) {//分解质因数
    		for (int j = 1; j <= prime[0]; j++) {
    			x = i;
    			while (x % prime[j] == 0) {
    				cnt[i][j]++;
    				x /= prime[j];
    			}
    			st[i][j] = cnt[i][j];//状态压缩,01表示是否含有质因数
    		}
    	}
    	int n, m;
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) {
    		cin >> w[i];
    	}
    	build(1, 1, n);
    	int op, opl, opr, x;
    	while (m--) {
    		cin >> op >> opl >> opr;
    		if (op) {
    			ans[++ans[0]] = query(1, 1, n, opl, opr);
    		}
    		else {
    			cin >> x;
    			for (int i = 1; i <= prime[0]; i++) {//每次修改的是该数对应的所有质因数及其次数
    				if (cnt[x][i]) {
    					modify(1, 1, n, opl, opr, { i,cnt[x][i] });
    				}
    			}
    		}
    	}
    	for (int i = 1; i < ans[0]; i++) {
    		cout << ans[i] << endl;
    	}
    	if (ans[0]) {
    		cout << ans[ans[0]];
    	}
    	return 0;
    }
    
    

    简单练习

    ​ 本来只是准备了上面三道题的,在整理的过程中发现自己以前做过的题中还有一道也运用了势能线段树的思想,而且比上面三道题都要简单,有兴趣的同学可以去看一下

    ​ 题目来源:2021东北四省赛 D Lowbit(HDU7116

    参考文献

    https://blog.csdn.net/Daniel__d/article/details/105104831

    https://blog.csdn.net/qq_33969563/article/details/120497762

    展开全文
  • 势能线段树

    千次阅读 2020-03-25 21:24:34
    势能线段树 解析 区间开方 例题P4145 题目描述 题解 代码 #include<bits/stdc++.h> #define M 200009 #define int long long using namespace std; int read(){ int f=1,re=0;char ch; for(ch=getchar();!...

    势能线段树

    解析

    我们知道,线段树能够通过打标记实现区间修改的条件有两个:
    1,能够快速处理标记对区间询问结果的影响
    2,能够快速实现标记的合并
    但有的区间修改不满足上面两个条件(如区间开方,区间取模等)
    但某些修改存在一些奇妙的性质,使得序列每个元素被修改的次数有一个上限
    可以在线段树每个节点上记录一个值,表示对应区间内是否每个元素都达到修改次数上限
    区间修改时暴力递归到叶子节点,如果途中遇到一个节点,这个节点的对应区间内每个元素都达到修改次数上限则在这个节点 r e t u r n return return
    可以证明复杂度为 O ( n l o g n × O(nlogn× O(nlogn×修改次数上限 ) ) )
    用几个简单的例题说明一下

    区间开方

    例题P4145

    题目描述

    题目描述

    题解

    区间开方
    我们可以发现对 1 1 1 0 0 0的开方,对他的值是不会改变的,因此我们维护一个区间最大值,如果该区间的最大值 > 1 >1 >1,那么再递归下去。
    复杂度分析:
    显然,手玩一下就会发现一个数不超过 5 5 5次开方,就会变为 0 0 0 1 1 1,因此是完全 o k ok ok

    代码

    #include<bits/stdc++.h>
    #define M 200009
    #define int long long 
    using namespace std;
    int read(){
    	int f=1,re=0;char ch;
    	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    	if(ch=='-'){f=-1,ch=getchar();}
    	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
    	return re*f;
    }
    int n,m,a[M];
    struct tree{int l,r,maxn,sum;}tr[M*4];
    void pushup(int k){
    	tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn);
    	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
    }
    void build(int k,int l,int r){
    	tr[k].l=l,tr[k].r=r;
    	if(l==r){
    		tr[k].sum=tr[k].maxn=a[l];
    		return;
    	}int mid=(l+r)>>1;
    	build(k<<1,l,mid);
    	build(k<<1|1,mid+1,r);
    	pushup(k);
    }
    void update(int k,int l,int r){
    	if(tr[k].l==tr[k].r){
    		tr[k].maxn=sqrt(tr[k].maxn);
    		tr[k].sum=tr[k].maxn;
    		return;
    	}int mid=(tr[k].l+tr[k].r)>>1;
    	if(l<=mid&&tr[k<<1].maxn>1) update(k<<1,l,r);
    	if(r>mid&&tr[k<<1|1].maxn>1) update(k<<1|1,l,r);
    	pushup(k);
    }
    int query(int k,int l,int r){
    	if(tr[k].l>=l&&tr[k].r<=r) return tr[k].sum;
    	int mid=(tr[k].l+tr[k].r)>>1,ret=0;
    	if(l<=mid) ret+=query(k<<1,l,r);
    	if(r>mid) ret+=query(k<<1|1,l,r);
    	return ret;
    }
    signed main(){
    	n=read();
    	for(int i=1;i<=n;i++) a[i]=read();
    	build(1,1,n),m=read();
    	for(int i=1;i<=m;i++){
    		int opt=read(),l=read(),r=read();
    		if(l>r) swap(l,r);
    		if(opt==0) update(1,l,r);
    		if(opt==1) printf("%lld\n",query(1,l,r));
    	}return 0;
    }
    

    区间取模

    例题 CF438D

    题解

    区间取模
    我们仍然考虑维护区间最大值,如果当前区间的最大值小于模数p,那么不用再递归下去了,因为值是不会改变的。
    复杂度分析:
    显然一个数每次取模都至少减小一半,那么复杂度也就为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

    代码

    #include<bits/stdc++.h>
    #define int long long
    #define M 100009
    using namespace std;
    int read(){
    	int f=1,re=0;char ch;
    	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    	if(ch=='-'){f=-1,ch=getchar();}
    	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
    	return re*f;
    }
    int n,m,a[M];
    struct tree{int l,r,maxn,sum;}tr[M*4];
    void pushup(int k){
    	tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn);
    	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
    }
    void build(int k,int l,int r){
    	tr[k].l=l,tr[k].r=r;
    	if(l==r){
    		tr[k].sum=tr[k].maxn=a[l];
    		return;
    	}int mid=(l+r)>>1;
    	build(k<<1,l,mid);
    	build(k<<1|1,mid+1,r);
    	pushup(k);
    }
    void update(int k,int l,int r,int p){
    	if(tr[k].l==tr[k].r){
    		tr[k].maxn=tr[k].maxn%p;
    		tr[k].sum=tr[k].maxn;
    		return;
    	}int mid=(tr[k].l+tr[k].r)>>1;
    	if(l<=mid&&tr[k<<1].maxn>=p) update(k<<1,l,r,p);
    	if(r>mid&&tr[k<<1|1].maxn>=p) update(k<<1|1,l,r,p);
    	pushup(k);
    }
    void change(int k,int pos,int val){
    	if(tr[k].l==tr[k].r){
    		tr[k].maxn=tr[k].sum=val;
    		return;
    	}int mid=(tr[k].l+tr[k].r)>>1;
    	if(pos<=mid) change(k<<1,pos,val);
    	else change(k<<1|1,pos,val);
    	pushup(k);
    }
    int query(int k,int l,int r){
    	if(tr[k].l>=l&&tr[k].r<=r) return tr[k].sum;
    	int mid=(tr[k].l+tr[k].r)>>1,ret=0;
    	if(l<=mid) ret+=query(k<<1,l,r);
    	if(r>mid) ret+=query(k<<1|1,l,r);
    	return ret;
    }
    signed main(){
    	n=read(),m=read();
    	for(int i=1;i<=n;i++) a[i]=read();
    	build(1,1,n);
    	for(int i=1;i<=m;i++){
    		int opt=read(),l=read(),r=read(),p;
    		if(opt==1) printf("%lld\n",query(1,l,r));
    		if(opt==2) p=read(),update(1,l,r,p);
    		if(opt==3) change(1,l,r);
    	}return 0;
    }
    

    其他区间操作

    例题1CF920F

    题目描述

    题目描述

    题解

    显然这样的操作也不能直接合并,但是我们发现当该区间的最大值小于 3 3 3时,再次操作也不会改变他的值,因此我们只需要预处理出来 1 e 6 1e6 1e6个数的约束个数(当然因为这是积性函数,也可以线性筛 O ( n ) O(n) O(n)求出),暴力修改即可。
    复杂度分析:
    因为 D ( x ) D(x) D(x)最多为 x / 2 x/2 x/2,因此复杂度也为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)

    代码

    #include<bits/stdc++.h>
    #define int long long
    #define M 300009 
    using namespace std;
    int read(){
    	int f=1,re=0;char ch;
    	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    	if(ch=='-'){f=-1,ch=getchar();} 
    	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
    	return re*f;
    }
    int n,m,a[M],p[M*4];
    struct tree{int l,r,sum,maxn;}tr[M*4];
    void pushup(int k){
    	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
    	tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn);
    }
    void build(int k,int l,int r){
    	tr[k].l=l,tr[k].r=r;
    	if(l==r){
    		tr[k].sum=tr[k].maxn=a[l];
    		return;
    	}int mid=(l+r)>>1;
    	build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    	pushup(k);
    }
    void update(int k,int ql,int qr){
    	if(tr[k].l==tr[k].r){tr[k].sum=tr[k].maxn=p[tr[k].maxn];return;}
    	int mid=(tr[k].l+tr[k].r)>>1;
    	if(ql<=mid&&tr[k<<1].maxn>2) update(k<<1,ql,qr);
    	if(qr>mid&&tr[k<<1|1].maxn>2) update(k<<1|1,ql,qr);
    	pushup(k);
    }
    int query(int k,int ql,int qr){
    	if(tr[k].l>=ql&&tr[k].r<=qr) return tr[k].sum;
    	int mid=(tr[k].l+tr[k].r)>>1,ret=0;
    	if(ql<=mid) ret+=query(k<<1,ql,qr);
    	if(qr>mid) ret+=query(k<<1|1,ql,qr);
    	return ret;
    }
    signed main(){
    	n=read(),m=read();
    	for(int i=1;i<=1000000;i++)
    		for(int j=i;j<=1000000;j+=i) p[j]++;
    	for(int i=1;i<=n;i++) a[i]=read();
    	build(1,1,n);
    	for(int i=1;i<=m;i++){
    		int opt=read(),x=read(),y=read();
    		if(x>y) swap(x,y);
    		if(opt==1) update(1,x,y);
    		else printf("%lld\n",query(1,x,y));
    	}return 0;
    }
    

    例题2 LOJ6029

    题解

    区间除
    我们发现对于一个序列,如果除的前后,最大值的变化量 = = == ==最小值的变化量,那么其实这就是一个区间减的操作(因为显然这个变化量是有单调性的),因此我们只需要维护区间最大值和区间最大值即可,然后暴力修改,遇到满足条件的就区间减,然后直接 r e t u r n return return

    代码

    #include<bits/stdc++.h>
    #define int long long
    #define M 100009
    using namespace std;
    int n,m,a[M];
    const int inf=1e18; 
    struct tree{int l,r,maxn,sum,minx,tag;}tr[M*4];
    int read(){
    	int f=1,re=0;char ch;
    	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    	if(ch=='-'){f=-1,ch=getchar();}
    	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
    	return re*f;
    }
    void add(int k,int val){
    	tr[k].tag+=val;
    	tr[k].sum+=val*(tr[k].r-tr[k].l+1);
    	tr[k].minx+=val;
    	tr[k].maxn+=val;
    }
    void pushdown(int k){
    	if(tr[k].tag){
    		add(k<<1,tr[k].tag);
    		add(k<<1|1,tr[k].tag);
    		tr[k].tag=0;
    	}
    }
    void pushup(int k){
    	tr[k].minx=min(tr[k<<1].minx,tr[k<<1|1].minx);
    	tr[k].maxn=max(tr[k<<1].maxn,tr[k<<1|1].maxn);
    	tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
    }
    void build(int k,int l,int r){
    	tr[k].l=l,tr[k].r=r;
    	tr[k].minx=inf,tr[k].maxn=-inf;
    	if(l==r){
    		tr[k].sum=tr[k].maxn=tr[k].minx=a[l];
    		return;
    	}int mid=(l+r)>>1;
    	build(k<<1,l,mid);
    	build(k<<1|1,mid+1,r);
    	pushup(k);
    }
    void update(int k,int l,int r,int p){
    	if(tr[k].l>=l&&tr[k].r<=r){
    		int fx=tr[k].maxn-(long long)floor((double)tr[k].maxn/p);
    		int fy=tr[k].minx-(long long)floor((double)tr[k].minx/p);
    		if(fx==fy) return add(k,-fx);
    	}int mid=(tr[k].l+tr[k].r)>>1;
    	pushdown(k);
    	if(l<=mid) update(k<<1,l,r,p);
    	if(r>mid) update(k<<1|1,l,r,p);
    	pushup(k);
    }
    void change(int k,int l,int r,int p){
    	if(tr[k].l>=l&&tr[k].r<=r) return add(k,p);
    	int mid=(tr[k].l+tr[k].r)>>1;
    	pushdown(k);
    	if(l<=mid) change(k<<1,l,r,p);
    	if(r>mid) change(k<<1|1,l,r,p);
    	pushup(k);
    }
    int solve(int k,int l,int r){
    	if(tr[k].l>=l&&tr[k].r<=r) return tr[k].minx;
    	pushdown(k);
    	int mid=(tr[k].l+tr[k].r)>>1,ret=inf;
    	if(l<=mid) ret=min(ret,solve(k<<1,l,r));
    	if(r>mid) ret=min(ret,solve(k<<1|1,l,r));
    	pushup(k);return ret;
    }
    int query(int k,int l,int r){
    	if(tr[k].l>=l&&tr[k].r<=r) return tr[k].sum;
    	pushdown(k);
    	int mid=(tr[k].l+tr[k].r)>>1,ret=0;
    	if(l<=mid) ret+=query(k<<1,l,r);
    	if(r>mid) ret+=query(k<<1|1,l,r);
    	pushup(k);return ret;
    }
    signed main(){
    	n=read(),m=read();
    	for(int i=1;i<=n;i++) a[i]=read();
    	build(1,1,n);
    	for(int i=1;i<=m;i++){
    		int opt=read(),l=read()+1,r=read()+1,x;
    		if(opt==1) x=read(),change(1,l,r,x);
    		if(opt==2) x=read(),update(1,l,r,x);
    		if(opt==3) printf("%lld\n",solve(1,l,r));
    		if(opt==4) printf("%lld\n",query(1,l,r));
    	}return 0;
    }
    
    展开全文
  • 势能线段树模板题二

    2021-09-16 23:03:42
    题目地址 配套地址 确定 0 势能点为 最大值和最小值的差值为0,有区间修改操作,所以要维护懒标记。 注意优化,当某一次取根操作使得最大值和最小值减小的值一样,可以看成区间加负数,不是则暴力递推下去。 时间...

    题目地址
    配套地址

    在这里插入图片描述

    确定 0 势能点为 最大值和最小值的差值为0,有区间修改操作,所以要维护懒标记。

    注意优化,当某一次取根操作使得最大值和最小值减小的值一样,可以看成区间加负数,不是则暴力递推下去。

    时间复杂度证明为 O ( m l o g 2 n ) O(mlog^2n) O(mlog2n)

    #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    const int mod = 998244353;
    //#define int long long
    typedef long long ll;
    
    int a[N];
    
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define mn(x) t[x].mn
    #define mx(x) t[x].mx
    #define add(x) t[x].add
    #define sum(x) t[x].sum
    
    struct SegmentTree {
        int l,r;
        ll mn,mx;
        ll add,sum;
    }t[N << 2];
    
    #define lson(x) (x<<1)
    #define rson(x) (x<<1|1)
    
    void push_up(int p) {
        sum(p) = sum(lson(p)) + sum(rson(p));
        mn(p) = min(mn(lson(p)),mn(rson(p)));
        mx(p) = max(mx(lson(p)),mx(rson(p)));
    }
    
    void ADD(int p,ll v) {
        sum(p) += v * (r(p) - l(p) + 1);
        add(p) += v;
        mn(p) += v;
        mx(p) += v;
    }
    
    void push_down(int p) {
        ADD(lson(p),add(p));
        ADD(rson(p),add(p));
        add(p) = 0;
    }
    
    void build(int p,int l,int r) {
        l(p) = l,r(p)= r;
        if(l == r) {
            mn(p) = mx(p) = sum(p) = a[l];
            add(p) = 0;
            return ;
        }
        int mid = l + r >> 1;
        build(lson(p),l,mid); build(rson(p),mid+1,r);
        push_up(p);
    }
    
    void update_sqrt(int p,int l,int r) {
        if(l <= l(p) && r >= r(p)) {
            ll fmn = mn(p) - (int)sqrt(mn(p));
            ll fmx = mx(p) - (int)sqrt(mx(p));
            if(fmn == fmx) return ADD(p,-fmx);
        }
        push_down(p);
        int mid = (l(p) + r(p)) >> 1;
        if(l <= mid) update_sqrt(lson(p),l,r);
        if(r > mid) update_sqrt(rson(p),l,r);
        push_up(p);
    }
    
    void update_add(int p,int l,int r,int v) {
        if(l <= l(p) && r >= r(p)) return ADD(p,v);
        push_down(p);
        int mid = (l(p) + r(p)) >> 1;
        if(l <= mid) update_add(lson(p),l,r,v);
        if(r > mid) update_add(rson(p),l,r,v);
        push_up(p);
    }
    
    ll query(int p,int l,int r) {
        if(l <= l(p) && r >= r(p)) return sum(p);
        ll res = 0;
        push_down(p);
        int mid = (l(p) + r(p)) >> 1;
        if(l <= mid) res += query(lson(p),l,r);
        if(r > mid) res += query(rson(p),l,r);
        return res;
    }
    
    signed main(){
    	IOS
    	#ifdef ddgo
    		freopen("C:\\Users\\asus\\Desktop\\ddgoin.txt","r",stdin);
        #endif
        int n,m; cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n);
        while(m --) {
            int op,l,r; cin>>op>>l>>r;
            if(op == 1) {
                update_sqrt(1,l,r);
            }else if(op == 2) {
                int x; cin>>x;
                update_add(1,l,r,x);
            }else {
                cout<<query(1,l,r)<<endl;
            }
        }
    	return 0;
    }
    
    展开全文
  • 势能线段树专题

    2021-10-04 09:24:18
    牛客竞赛数据结构专题班势能线段树、李超线段树 势能线段树模板题一 我们没有办法直接对区间进行开方然后下传,所以pushdown就没必要写了。 对于每个数,开方6次之后达到势能上限,其结果必然为0或者1。那么对于整个...

    牛客竞赛数据结构专题班势能线段树、李超线段树
    zngg的题解

    势能线段树模板题一
    题意:
    操作一:对区间 [ l , r ] [l,r] [l,r] 每个数 x x x x \sqrt{x} x
    操作二:求区间 [ l , r ] [l,r] [l,r] 的和

    思路一:
    我们没有办法直接对区间进行开方然后下传,所以pushdown就没必要写了。
    对于每个数,开方6次之后达到势能上限,其结果必然为0或者1。那么对于整个区间,
    可以记录开方次数(取区间内开方次数最少的那个值)是否达到6就可以了,
    或者只要一个区间全为0或1的话,也可以直接返回。
    code:

    #include<bits/stdc++.h>
    #define ll long long
    #define lc (p << 1)
    #define rc (p << 1 | 1)
    #define endl '\n'
    using namespace std;
    const int maxn = 2e5 + 9;
    int n, m;
    ll tr[maxn << 2], cnt[maxn << 2];
    inline void pushup(int p)
    {
    	tr[p] = tr[lc] + tr[rc];
    	cnt[p] = min(cnt[lc], cnt[rc]);
    }
    void build(int p = 1, int cl = 1, int cr = n)
    {
    	if(cl == cr){
    		cin >> tr[p];
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	build(lc, cl, mid);
    	build(rc, mid + 1, cr);
    	pushup(p);
    }
    ll query(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(cl >= l && cr <= r) return tr[p];
    	ll mid = (cl + cr) >> 1, ans = 0;
    	if(mid >= l) ans += query(l, r, lc, cl, mid);
    	if(mid < r) ans += query(l, r, rc, mid + 1, cr);
    	return ans;
    }
    void update(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(cnt[p] > 5) return;
    	if(cl == cr){
    		tr[p] = (int)sqrt(tr[p]);
    		++cnt[p];
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	if(mid >= l) update(l, r, lc, cl, mid);
    	if(mid < r) update(l, r, rc, mid + 1, cr);
    	pushup(p);
    }
    void work()
    {
    	cin >> n >> m;
    	build();
    	while(m--)
    	{
    		int op, l, r;cin >> op >> l >> r;
    		if(op == 1) update(l, r);
    		else cout << query(l, r) << endl;
    	}
    }
    
    int main()
    {
    	ios::sync_with_stdio(0);
    	work();
    	return 0;
    }
    

    思路二:
    框架基本一样
    维护区间最大值,如果区间最大值为 1 1 1,则没必要修改
    code:

    #include<bits/stdc++.h>
    #define ll long long
    #define lc (p << 1)
    #define rc (p << 1 | 1)
    #define endl '\n'
    using namespace std;
    const int maxn = 2e5 + 9;
    const ll inf = 0x3f3f3f3f3f3f;
    int n, m;
    ll tr[maxn << 2], Max[maxn << 2];
    inline void pushup(int p)
    {
    	tr[p] = tr[lc] + tr[rc];
    	Max[p] = max(Max[lc], Max[rc]);
    }
    void build(int p = 1, int cl = 1, int cr = n)
    {
    	Max[p] = - inf;// 因为 ai 始终是正的,所以不置为 -inf,初始全是 0 也是一样的
    	if(cl == cr){
    		cin >> tr[p];
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	build(lc, cl, mid);
    	build(rc, mid + 1, cr);
    	pushup(p);
    }
    ll query(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(cl >= l && cr <= r) return tr[p];
    	ll mid = (cl + cr) >> 1, ans = 0;
    	if(mid >= l) ans += query(l, r, lc, cl, mid);
    	if(mid < r) ans += query(l, r, rc, mid + 1, cr);
    	return ans;
    }
    void update(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(Max[p] == 1) return;
    	if(cl == cr){
    		tr[p] = (int)sqrt(tr[p]);
    		Max[p] = tr[p];
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	if(mid >= l) update(l, r, lc, cl, mid);
    	if(mid < r) update(l, r, rc, mid + 1, cr);
    	pushup(p);
    }
    void work()
    {
    	cin >> n >> m;
    	build();
    	while(m--)
    	{
    		int op, l, r;cin >> op >> l >> r;
    		if(op == 1) update(l, r);
    		else cout << query(l, r) << endl;
    	}
    }
    
    int main()
    {
    	ios::sync_with_stdio(0);
    	work();
    	return 0;
    }
    
    

    势能线段树模板题二
    题意:
    操作一:对区间 [ l , r ] [l,r] [l,r] 每个数 x x x x \sqrt{x} x
    操作二:对区间 [ l , r ] [l,r] [l,r] 每个数 加 c c c
    操作三:求区间 [ l , r ] [l,r] [l,r] 的和
    思路:
    带修改的区间开方
    我们发现对于一个序列,如果开方的前后,最大值的变化量等于最小值的变化量,那么其实这就是一个区间减的操作(因为显然这个变化量是有单调性的),因此我们只需要维护区间最大值和区间最大值即可,然后暴力修改,遇到满足条件的就区间减,然后直接return

    code:

    #include<bits/stdc++.h>
    #define ll long long
    #define lc (p << 1)
    #define rc (p << 1 | 1)
    #define endl '\n'
    using namespace std;
    const int maxn = 2e5 + 9;
    const ll inf = 0x3f3f3f3f3f3f;
    ll n, m;
    ll a[maxn];
    struct node
    {
    	ll add, sum, Max, Min;
    }tr[maxn << 2];
    
    inline void addlazy(int p, int len, ll x)
    {
    	tr[p].add += x;
    	tr[p].sum += 1ll * len * x;
    	tr[p].Max += x;
    	tr[p].Min += x;
    }
    inline void pushup(int p)
    {
    	tr[p].sum = tr[lc].sum + tr[rc].sum;
    	tr[p].Max = max(tr[lc].Max, tr[rc].Max);
    	tr[p].Min = min(tr[lc].Min, tr[rc].Min);
    }
    inline void pushdown(int p, int len)
    {
    	if(!tr[p].add) return;
    	addlazy(lc, len - len / 2, tr[p].add);
    	addlazy(rc, len / 2, tr[p].add);
    	tr[p].add = 0;
    }
    void build(int p = 1, int cl = 1, int cr = n)
    {
    	tr[p].Max = -inf; tr[p].Min = inf;
    	if(cl == cr){
    		tr[p].Max = tr[p].Min = tr[p].sum = a[cl];
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	build(lc, cl, mid);
    	build(rc, mid + 1, cr);
    	pushup(p);
    }
    ll query(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(cl >= l && cr <= r) return tr[p].sum;
    	pushdown(p, cr - cl + 1);
    	ll mid = (cl + cr) >> 1, ans = 0;
    	if(mid >= l) ans += query(l, r, lc, cl, mid);
    	if(mid < r) ans += query(l, r, rc, mid + 1, cr);
    	return ans;
    }
    void update(int l, int r, ll d, int p = 1, int cl = 1, int cr = n)
    {
    	if(cl >= l && cr <= r){
    		if(d == -1)
    		{
    			ll fx = tr[p].Max - (ll)sqrt(tr[p].Max);
    			ll fy = tr[p].Min - (ll)sqrt(tr[p].Min);
    			if(fx == fy) {
    				addlazy(p, cr - cl + 1, -fx);return;
    			}
    		}
    		else if(d != -1) {
    			addlazy(p, cr - cl + 1, d);return;
    		}
    	}
    	pushdown(p, cr - cl + 1);
    	int mid = (cl + cr) >> 1;
    	if(mid >= l) update(l, r, d, lc, cl, mid);
    	if(mid < r) update(l, r, d, rc, mid + 1, cr);
    	pushup(p);
    }
    void work()
    {
    	cin >> n >> m;
    	for(int i = 1; i <= n; ++i) cin >> a[i];
    	build();
    	while(m--)
    	{
    		ll op, l, r;cin >> op >> l >> r;
    		if(op == 1) update(l, r, -1);
    		else if(op == 2){
    			ll k;cin >> k; update(l, r, k);
    		}
    		else cout << query(l, r) << endl;
    	}
    }
    
    int main()
    {
    	ios::sync_with_stdio(0);
    	work();
    	return 0;
    }
    

    Gorgeous Sequence
    题意:
    三个操作

    1. 对区间 [ l , r ] [l,r] [l,r] ,每个数与 t t t m i n min min,即 a i = m i n ( a i , t ) a_i=min(a_i,t) ai=min(ai,t)
    2. 查询区间 [ l , r ] [l,r] [l,r] 最大值
    3. 查询区间 [ l , r ] [l,r] [l,r] 所有元素之和

    思路:
    区间取 m i n min min,意味着只对那些大于 t t t 的数有更改。因此这个操作的对象不再是整个区间,而是“这个区间中大于 t t t 的数”。于是我们可以有这样的思路:每个结点维护该区间的最大值 M a x Max Max 、次大值 S e m a x Semax Semax、区间和 S u m Sum Sum 以及最大值的个数 C n t Cnt Cnt。接下来我们考虑区间对 t t t m i n min min 的操作。

    1. 如果 M a x < = t Max<=t Max<=t,显然这个 t t t 是没有意义的,直接 r e t u r n return return
    2. 如果 S e m a x < t < M a x Semax<t<Max Semax<t<Max,那么这个 t t t 就能更新当前区间中的最大值。于是我们让区间和加上 C n t ∗ ( t − M a x ) Cnt*(t-Max) Cnt(tMax),然后更新 M a x Max Max t t t,并打一个标记。
    3. 如果 t < = S e m a x t<=Semax t<=Semax,这种情况我们不知道涉及多少数的过呢更新,就暴力递归向下操作,然后上传信息。

    复杂度 O ( m   l o g   n ) O(m \ log \ n) O(m log n)
    code:

    #include<bits/stdc++.h>
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    #define ll long long
    using namespace std;
    const int maxn = 1e6 + 9;
    int n, m;
    struct node
    {
    	ll sum;
    	int Max, Semax, cnt, mark;	
    }tr[maxn << 2];
    inline void pushlazy(int p, int x)
    {
    	if(tr[p].Max <= x) return;
    	tr[p].sum += (1ll * x - tr[p].Max) * tr[p].cnt;
    	tr[p].Max = tr[p].mark = x;
    }
    inline void pushdown(int p)
    {
    	if(tr[p].mark == -1) return;
    	pushlazy(ls, tr[p].mark);
    	pushlazy(rs, tr[p].mark);
    	tr[p].mark = -1;
    }
    inline pushup(int p)
    {
    	tr[p].sum = tr[ls].sum + tr[rs].sum;
    	if(tr[ls].Max == tr[rs].Max)
    	{
    		tr[p].Max = tr[ls].Max;
    		tr[p].Semax = max(tr[ls].Semax, tr[rs].Semax);
    		tr[p].cnt = tr[ls].cnt + tr[rs].cnt;
    	}
    	else if(tr[ls].Max > tr[rs].Max)
    	{
    		tr[p].Max = tr[ls].Max;
    		tr[p].Semax = max(tr[ls].Semax, tr[rs].Max);
    		tr[p].cnt = tr[ls].cnt;
    	}
    	else 
    	{
    		tr[p].Max = tr[rs].Max;
    		tr[p].Semax = max(tr[ls].Max, tr[rs].Semax);
    		tr[p].cnt = tr[rs].cnt;
    	}
    }
    void build(int p = 1, int cl = 1, int cr = n)
    {
    	tr[p].mark = -1;
    	if(cl == cr){
    		cin >> tr[p].sum;
    		tr[p].Max = tr[p].sum;
    		tr[p].cnt = 1;
    		tr[p].Semax = -1;
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	build(ls, cl, mid);
    	build(rs, mid + 1, cr);
    	pushup(p);
    }
    void update(int l, int r, int d, int p = 1, int cl = 1, int cr = n)
    {
    	if(tr[p].Max <= d) return;
    	if(cl >= l && cr <= r && tr[p].Semax < d){
    		pushlazy(p, d);
    		return;
    	}
    	int mid = (cl + cr) >> 1;
    	pushdown(p);
    	if(mid >= l) update(l, r, d, ls, cl, mid);
    	if(mid < r) update(l, r, d, rs, mid + 1, cr);
    	pushup(p);
    }
    int query_max(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(cl >= l && cr <= r) return tr[p].Max;
    	int mid = (cl + cr) >> 1, ans1 = -1, ans2 = -1;
    	pushdown(p);
    	if(mid >= l) ans1 = max(ans1, query_max(l, r, ls, cl, mid));
    	if(mid < r) ans2 = max(ans2, query_max(l, r, rs, mid + 1, cr));
    	return max(ans1, ans2);
    }
    ll query_sum(int l, int r, int p = 1, int cl = 1, int cr = n)
    {
    	if(cl >= l && cr <= r) return tr[p].sum;
    	pushdown(p);
    	ll mid = (cl + cr) >> 1, ans = 0;
    	if(mid >= l) ans += query_sum(l, r, ls, cl, mid);
    	if(mid < r) ans += query_sum(l, r, rs, mid + 1, cr);
    	return ans;
    }
    void work()
    {
    	cin >> n >> m;
    	build();
    	while(m--)
    	{
    		int op, l, r, d;
    		cin >> op >> l >> r;
    		if(!op){
    			cin >> d; update(l, r, d);
    		}
    		else if(op == 1) cout << query_max(l, r) << endl;
    		else cout << query_sum(l, r) << endl;
    	}
    }
    
    int main()
    {
    	ios::sync_with_stdio(0);
    	int TT;cin>>TT;while(TT--)
    	work();
    	return 0;
    }
    
    展开全文
  • 势能线段树 势能线段树 势能: 信息学中,势能被用于计算某一个过程,或者某一类过程时间复杂度的总和 例如计算两个数之间的最大公倍数gcd的时间复杂度是O(log N),而计算n个数之间的时间复杂度是O(n+log N) 总...
  • 吉司机最经典的应用,区间最值更新 HDU 5306 其中对最大值和次大值及其个数的维护方式值得学习 #include<bits/stdc++.h> using namespace std; #define go(i,a,b) for(int i=a;...#defin...
  • 势能线段树 维护区间不为1的元素数量 对于存在元素不为1的区间暴力递归修改/************************************************************** Problem: 3211 User: di4CoveRy Language: C++ Result: Accepted...
  • 吉老师线段树 感觉就是普通的线段树+暴力 常见的套路有区间取模,区间开根等 因为我做题少就见过这俩 你也看见题目上的Ⅰ了,碰到再更新 所以为什么叫吉老师线段树,为什么不叫老头子线段树 于是我去学习了一下历史 ...
  • 线段树分裂 以某个键值为中点将线段树分裂成左右两部分,应该类似Treap的分裂吧(我菜不会Treap)。一般应用于区间排序。 方法很简单,就是把分裂之后的两棵树的重复的\(\log\)个节点新建出来,单次时间复杂度严格\...
  • 序列[势能线段树]

    2019-10-21 19:50:40
    机房某大佬告诉咱这是势能线段树? 对于每个 i i i ,每被加 b i b_i b i ​ 次就产生 1 1 1 的贡献,考虑维护这个过程 用一颗线段树,维护每个点的最大值和最大值在那个子树 每个节点的初值设为 − b i -b_i − b i ...
  • 我们用线段树维护区间和的同时维护一下这个区间内的颜色是否全部相同,如果全部相同,那么我们去进行区间修改,如果不相同,那么继续向下递归,直到找到相等的区间 代码 #pragma GCC optimize(3) #include <bits/...
  • 直接在线段树上维护最大值和最小值,每次递归更新的时候,如果不能完全覆盖就暴力递归下去。挺好写的欸 鉴于上次写冒险常数太大的经历,蒟蒻这次来个码风奇特的指针线段树 #include<bits/stdc++.h> #define RG...
  • 树链剖分模板 +势能线段树势能线段树大佬博客) #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const int...
  • 洛谷题目传送门 闲话 考场上一眼看出这是个毒瘤线段树准备杠题,发现...蒟蒻一开始往势能线段树上面想了想。 定义一个全局势能函数,为所有\(C_i<B_i\)的位置个数。注意两个操作的修改都不会小于原来的数。 一个...
  • 表示蒟蒻并不能一眼看出来这是个势能线段树。 不过仔细想想也并非难以理解,感性理解一下,在一个区间里又与又或,那么本来不相同的位也会渐渐相同,线段树每个叶子节点最多修改\(\log a\)次(\(a\)为值域)。 那么...
  • 顺便去补补2-3道势能线段树。 #include #include #include #include #include #include #include #include const int maxn = 1e5+5; using namespace std; #define lson l,m,rt #define rson m+1,r,rt|...
  • CF 441 C 题意 给你一个n个元素的序列 首先第 i 个坐标的颜色值是 i 然后你有两个操作 1 是 给 x y 颜色区间赋值成 v 然后给他们的每个点权值加上新颜色 和 之前颜色的绝对值之差 2 是求 x 到 y 的点权值之和 ...
  • 思路:势能线段树,因为n所以最多开方5次即可结束变为1(可以不使用lazy延迟标记),暴力更新即可 #include #include #include #include #include #include #include #include #define lson l,m,rt #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 439
精华内容 175
关键字:

势能线段树