首页 > 其他分享 >线段树 transformation——hdu 4578

线段树 transformation——hdu 4578

时间：2024-09-10 19:47:36浏览次数：9  
标签：hdu int segTree sum2 add 4578 操作 include transformation

问题描述：
给定一个数列，数列中所有元素都初始化为0，对其执行多种区间操作
操作1：add修改：对区间[L,R]内的所有数加c
操作2：multi修改：对区间[L,R]内所有数乘以c
操作3：change操作：把区间[L,R]内所有数改为c
操作4：sum操作：对区间中的每个数的p次方求和。1<=p<=3
输入：
有不超过10个测试用例。
对于每个测试用例，第一行包含两个数字n和m，表示有n个整数和m个操作。其中，1 <= n, m <= 100,000。
接下来的m行，每行包含一个操作。操作1到3的格式为："1 x y c" 或 "2 x y c" 或 "3 x y c"。操作4的格式为："4 x y p"。
（其中，1 <= x <= y <= n，1 <= c <= 10,000，1 <= p <= 3）
输入以0 0结束。
输出：
对于每个操作4，输出一个整数作为结果，每个结果占一行。答案可能非常大，你只需计算答案除以10007的余数即可。

题目分析：
本题考查对lazy_tag标记的理解，有三种修改操作三种查询操作，意味着需要三种tag标记，我们分别定义为add[],multi[]，change[]标记，需要知道的是他们在记录变化的时候，存在什么样的关系。
（1）做change修改时，原有的add和multi标记失效
（2）做multi修改时，如果原有add，则将add改为addmulti
（3）做线段树pushdown操作时，先处理change操作，后处理multi，最后执行add
三种查询操作，求和sum1，平方和sum2，立方和sum3。对于change和multi标记三种查询都很容易计算，对于add标记sum求和容易计算，但平方和与立方和需要推倒：
平方和sum2：
（a+c）2=a2+cc+2ac，即sum2[new]=sum2[old]+(R-L+1)cc+2sum1[old]c
立方和
（a+c）3=a3+ccc+3c(a**2+ac),即sum3[new]=sum3[old]+(R-L+1)ccc+3c(sum2[old]+sum1[old]c)
注：公式还需要结合操作二

代码：
来自园内大佬

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
using namespace std;
const int MOD = 10007;
const int MAXN = 100010;
struct Node {
	int l, r;
	int sum1, sum2, sum3;
	int lazy1, lazy2, lazy3;
} segTree[MAXN * 3];
void build(int i, int l, int r) {
	segTree[i].l = l;
	segTree[i].r = r;
	segTree[i].sum1 = segTree[i].sum2 = segTree[i].sum3 = 0;
	segTree[i].lazy1 = segTree[i].lazy3 = 0;
	segTree[i].lazy2 = 1;  //乘法标记为1
	int mid = (l + r) / 2;
	if (l == r)return;
	build(i << 1, l, mid);
	build((i << 1) | 1, mid + 1, r);
}
void push_up(int i) {
	if (segTree[i].l == segTree[i].r)
		return;
	segTree[i].sum1 = (segTree[i << 1].sum1 + segTree[(i << 1) | 1].sum1) % MOD;
	segTree[i].sum2 = (segTree[i << 1].sum2 + segTree[(i << 1) | 1].sum2) % MOD;
	segTree[i].sum3 = (segTree[i << 1].sum3 + segTree[(i << 1) | 1].sum3) % MOD;

}

void push_down(int i) {
	if (segTree[i].l == segTree[i].r) return;
	if (segTree[i].lazy3 != 0) {
		segTree[i << 1].lazy3 = segTree[(i << 1) | 1].lazy3 = segTree[i].lazy3;
		//加标记改为0，乘标记改为1即可将标记清除，将原有的标记清除
		segTree[i << 1].lazy1 = segTree[(i << 1) | 1].lazy1 = 0;
		segTree[i << 1].lazy2 = segTree[(i << 1) | 1].lazy2 = 1;
		//左孩子节点更新
		segTree[i << 1].sum1 = (segTree[i << 1].r - segTree[i << 1].l + 1) * segTree[i << 1].lazy3 % MOD;  //c
		segTree[i << 1].sum2 = (segTree[i << 1].r - segTree[i << 1].l + 1) * segTree[i << 1].lazy3 % MOD * segTree[i << 1].lazy3 % MOD;  //c*c
		segTree[i << 1].sum3 = (segTree[i << 1].r - segTree[i << 1].l + 1) * segTree[i << 1].lazy3 % MOD * segTree[i << 1].lazy3 % MOD * segTree[i << 1].lazy3 % MOD; //c*c*c
		//右孩子节点更新
		segTree[(i << 1) | 1].sum1 = (segTree[(i << 1) | 1].r - segTree[(i << 1) | 1].l + 1) * segTree[(i << 1) | 1].lazy3 % MOD;
		segTree[(i << 1) | 1].sum2 = (segTree[(i << 1) | 1].r - segTree[(i << 1) | 1].l + 1) * segTree[(i << 1) | 1].lazy3 % MOD * segTree[(i << 1) | 1].lazy3 % MOD;
		segTree[(i << 1) | 1].sum3 = (segTree[(i << 1) | 1].r - segTree[(i << 1) | 1].l + 1) * segTree[(i << 1) | 1].lazy3 % MOD * segTree[(i << 1) | 1].lazy3 % MOD * segTree[(i << 1) | 1].lazy3 % MOD;
		//标记传递后需要删除
		segTree[i].lazy3 = 0;
	}
	if (segTree[i].lazy1 != 0 || segTree[i].lazy2 != 1) {
		int sum1, sum2, sum3;
		//在做线段树pushdown操作时，先执行change，再执行multi，最后执行add
		
		//更新标记
		segTree[i << 1].lazy1 = (segTree[i].lazy2 * segTree[i << 1].lazy1 % MOD + segTree[i].lazy1) % MOD;
		segTree[i << 1].lazy2 = segTree[i << 1].lazy2 * segTree[i].lazy2 % MOD;

		//更新sum，在做线段树pushdown操作时，先执行change，再执行multi，最后执行add
		sum1 = (segTree[i << 1].sum1 * segTree[i].lazy2 % MOD + (segTree[i << 1].r - segTree[i << 1].l + 1) * segTree[i].lazy1 % MOD) % MOD;
		sum2 = (segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i << 1].sum2 % MOD + 2 * segTree[i].lazy1 * segTree[i].lazy2 % MOD * segTree[i << 1].sum1 % MOD + (segTree[i << 1].r - segTree[i << 1].l + 1) * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD) % MOD;
		sum3 = segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i << 1].sum3 % MOD;
		sum3 = (sum3 + 3 * segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i << 1].sum2) % MOD;
		sum3 = (sum3 + 3 * segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD * segTree[i << 1].sum1) % MOD;
		sum3 = (sum3 + (segTree[i << 1].r - segTree[i << 1].l + 1) * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD) % MOD;
		segTree[i << 1].sum1 = sum1;
		segTree[i << 1].sum2 = sum2;
		segTree[i << 1].sum3 = sum3;

		segTree[i << 1 | 1].lazy1 = (segTree[i].lazy2 * segTree[i << 1 | 1].lazy1 % MOD + segTree[i].lazy1) % MOD;
		segTree[i << 1 | 1].lazy2 = segTree[i << 1 | 1].lazy2 * segTree[i].lazy2 % MOD;

		sum1 = (segTree[i << 1 | 1].sum1 * segTree[i].lazy2 % MOD + (segTree[i << 1 | 1].r - segTree[i << 1 | 1].l + 1) * segTree[i].lazy1 % MOD) % MOD;
		sum2 = (segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i << 1 | 1].sum2 % MOD + 2 * segTree[i].lazy1 * segTree[i].lazy2 % MOD * segTree[i << 1 | 1].sum1 % MOD + (segTree[i << 1 | 1].r - segTree[i << 1 | 1].l + 1) * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD) % MOD;
		sum3 = segTree[i].lazy2 * segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i << 1 | 1].sum3 % MOD;
		sum3 = (sum3 + 3 * segTree[i].lazy2 % MOD * segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i << 1 | 1].sum2) % MOD;
		sum3 = (sum3 + 3 * segTree[i].lazy2 % MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD * segTree[i << 1 | 1].sum1) % MOD;
		sum3 = (sum3 + (segTree[i << 1 | 1].r - segTree[i << 1 | 1].l + 1) * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD * segTree[i].lazy1 % MOD) % MOD;
		segTree[i << 1 | 1].sum1 = sum1;
		segTree[i << 1 | 1].sum2 = sum2;
		segTree[i << 1 | 1].sum3 = sum3;

		//传递后需要清除标记
		segTree[i].lazy1 = 0;
		segTree[i].lazy2 = 1;

	}
}
void update(int i, int l, int r, int type, int c) {
	if (segTree[i].l >= l && segTree[i].r <= r) {
		//根据公式填写即可
		c %= MOD;
		if (type == 1) {
			segTree[i].lazy1 += c;
			segTree[i].lazy1 %= MOD;
			segTree[i].sum3 = (segTree[i].sum3 + 3 * segTree[i].sum2 % MOD * c % MOD + 3 * segTree[i].sum1 % MOD * c % MOD * c % MOD + (segTree[i].r - segTree[i].l + 1) * c % MOD * c % MOD * c % MOD) % MOD;
			segTree[i].sum2 = (segTree[i].sum2 + 2 * segTree[i].sum1 % MOD * c % MOD + (segTree[i].r - segTree[i].l + 1) * c % MOD * c % MOD) % MOD;
			segTree[i].sum1 = (segTree[i].sum1 + (segTree[i].r - segTree[i].l + 1) * c % MOD) % MOD;
		}
		else if (type == 2) {
			segTree[i].lazy1 = segTree[i].lazy1 * c % MOD;
			segTree[i].lazy2 = segTree[i].lazy2 * c % MOD;
			segTree[i].sum1 = segTree[i].sum1 * c % MOD;
			segTree[i].sum2 = segTree[i].sum2 * c % MOD * c % MOD;
			segTree[i].sum3 = segTree[i].sum3 * c % MOD * c % MOD * c % MOD;
		}
		else {
			segTree[i].lazy1 = 0;
			segTree[i].lazy2 = 1;
			segTree[i].lazy3 = c % MOD;
			segTree[i].sum1 = c * (segTree[i].r - segTree[i].l + 1) % MOD;
			segTree[i].sum2 = c * (segTree[i].r - segTree[i].l + 1) % MOD * c % MOD;
			segTree[i].sum3 = c * (segTree[i].r - segTree[i].l + 1) % MOD * c % MOD * c % MOD;
		}
		return;
	}
	push_down(i);
	//二分
	int mid = (segTree[i].l + segTree[i].r) / 2;
	if (l <= mid)update(i << 1, l, r, type, c);
	if (r > mid)update((i << 1) | 1, l, r, type, c);
	push_up(i);
}
int query(int i, int l, int r, int p) {
	if (segTree[i].l >= l && segTree[i].r <= r) {
		if (p == 1)return segTree[i].sum1;
		else if (p == 2)return segTree[i].sum2;
		else return segTree[i].sum3;
	}
	push_down(i);
	int mid = (segTree[i].l + segTree[i].r) / 2;
	int sum = 0;
	if (l <= mid) sum += query(i << 1, l, r, p);
	if (r > mid) sum += query((i << 1) | 1, l, r, p);
	return sum % MOD;
}

int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int n, m;
	while (scanf("%d%d", &n, &m) == 2) {
		if (n == 0 && m == 0)break;
		build(1, 1, n);
		int type, x, y, c;
		while (m--) {
			scanf("%d%d%d%d", &type, &x, &y, &c);
			if (type == 4)printf("%d\n", query(1, x, y, c));
			else update(1, x, y, type, c);
		}
	}
	return 0;
}

标签：hdu,int,segTree,sum2,add,4578,操作,include,transformation
From： https://www.cnblogs.com/oQAQo/p/18406461

相关文章

  • 线段树can you answer these queries-------hdu4027
    问题描述：给定一个数列，要求对指定区间内所有数开方，输出查询区间和输入：有很多个测试用例，每个用例第一行输出一个整数N，表示数列有N个数，1<=N<=100000;第二行输入N个整数E，E<2e63;第三行输入整数M，表示M种操作，1<=M<=100000;之后的M行，每行输入3个整数TXY。T=0，表示修改，将区间[L,R]内所......
  • HDU5512
    本题考察裴蜀定理，刚刚学过就写了一下。能够维修的塔就是\(a,b,a-b,a+b,a+2b,a-2b,2a-b,2a+b...\)，上述这些塔的位置就符合ax-by的格式，也就是可以使用裴蜀定理了。裴蜀定理为\(ax+by=gcd(a,b)\)，也就是说上述的所有能够维修的塔的位置都是\(gcd(a,b)\)的整数倍即为\(n/gcd(a,b)\)。那......
  • HDU 1729 Stone Game
    https://ac.nowcoder.com/acm/contest/34655/C有\(n\)个箱子，第\(i\)个箱子最多放\(s_i\)个石子，当前箱子里的石子数为\(c_i\)。两个人轮流往箱子里放石子，而且每一次放的数量都有限制：不能超过当前箱子内石子数的平方。例如箱子里有\(3\)颗石子，那么下一个人就可以放\(1-9\)......
  • 【hdu 7548】SunBian
    题目链接：hdu7548SunBian(2024“钉耙编程”中国大学生算法设计超级联赛（10）)思路：一道比较签到的题。先说结论：1.当n=k时A必胜2.当k=1时，n为奇数A胜，否则B胜3.其余情况全都为B胜证明：1.显然n=k时A可以一回合全部取完2.k=1时双方只能轮流来，显然奇数A胜偶数B胜3.此时A是......
  • hdu7438
    题面给定长度为\(N\)的序列\(a\)。一个序列有很多个子序列，每个子序列在序列中出现了若干次。小马想请你输出序列\(a\)每个非空子序列出现次数的立方值的和，答案对\(998244353\)取模。数据范围：\(n,a_i\le250\)。题解一个很高级的trick，"出现次数的立方值"等价于"我......
  • hdu7439
    题面小马给出长度为\(n\)的正整数序列\(f,g\)，现以如下方式生成\(n\)个点的有向图：forifrom1ton: forjfromi+1ton: iff[i]<f[j]andg[i]<g[j]: addedgefromitojelse: addedgefromjtoi试求出图中三元环的个数。数据范围：\(......
  • hdu2604
    用f(n)表示n个人满足条件的结果，那么如果最后一个人是m的话，那么前n-1个满足条件即可，就是f(n-1)； 如果最后一个是f那么这个还无法推出结果，那么往前再考虑一位：那么后三位可能是：mmf,fmf,mff,fff，其中fff和fmf不满足题意所以我们不考虑，但是如果是 mmf的话那么前n-3可以找满足条件的......
  • HDU-ACM 2024 Day4
    T1001超维攻坚(HDU7469)三维凸包，不会。T1002黑白边游戏(HDU7470)显然这道题没有一个固定的最优策略，所以只能\(\text{dp}\)决策。可以倒着做，设\(f_{i,S}\)表示从后往前进行了第\(i\simm\)轮，第\(i\)轮结束后（在原始意义下是开始前）黑边集合为\(S\)，双方使用最优策......
  • HDU 3590 PP and QQ
    题目链接：HDU3590【PPandQQ】思路    树上删边问题，套个反尼姆博弈。    反尼姆博弈是取走最后一个石子的人输掉游戏，所以需要特判一些特殊情况。    1.有堆的石子个数都是1，所以堆数为奇数时，先手必败，否则先手必胜    2.所有堆中存在石子数为......
  • HDU 2873 Bomb Game
    题目链接：HDU2873【BombGame】思路    数据范围较小，直接暴力求所有状态的SG值，然后将棋盘上所有炸弹的对应位置的SG值异或起来就可以得到当前局面的结果。对于相同位置的上有两个炸弹会自动爆炸，本来他们的SG值的异或和就为0，所以可以不用管。代码intn,m,vis[N*N......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99