首页 > 其他分享 >hdu - 4578(线段树)

hdu - 4578(线段树)

时间：2023-04-03 21:15:36浏览次数：38  
标签：hdu lc int 线段 tr tag rc 4578 sum

题目：Yuanfang is puzzled with the question below:
There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation ak<---ak+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation ak<---ak×c, k = x,x+1,…,y.
Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation ak<---c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of axp+ax+1p+…+ay p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: "1 x y c" or "2 x y c" or "3 x y c". Operation 4 is in this format: "4 x y p". (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

事先声明： tag_1为加， tag_2 为乘 ，tag_3 表示变为tag_3

思路：立方和与平方和

公式： 对一个区间都加上一个常数c

​ 已知： sum1 = a + b + c + ...... (n个数)

​ sum2 = a2 + b2 + c2 ......(n个数)

​ sum3 = a3 + b3 + c3 ...... (n个数)

​ 一次方和： sum1' = sum1 + n * c

​ 二次方和： sum2' = sum2 + 2 * sum1*c +n *c2 //平方和可得

​ 三次方和： sum3' = sum3 +3*sum2 * c + 3 * sum1 * c * c + n * c * c * c //立方和可得

注意事项：当有tag_2 ! = 1时,此时若有tag_1，则tag_1 *= c;

​ 当有tag_3时，此时将 tag_1赋值为0，tag_2 赋值为0 //显而易见的

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<deque>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 310000
#define N 200010
#define M 10007
#define endl '\n'
#define exp 1e-8
#define lc p << 1
#define rc p << 1|1
#define lowbit(x) ((x)&-(x))
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
inline ULL read() {
	ULL x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void print(ULL x) {
	if (x > 9)print(x / 10);
	putchar(x % 10 ^ 48);
}
struct node
{
	LL l, r, sum_1,sum_2,sum_3,tag_1,tag_2,tag_3;
}tr[4*N];
int n,m,cnt;
void pushup(int p)
{
	tr[p].sum_1 = (tr[lc].sum_1 + tr[rc].sum_1)%M;
	tr[p].sum_2 = (tr[lc].sum_2 + tr[rc].sum_2)%M;
	tr[p].sum_3 = (tr[lc].sum_3 + tr[rc].sum_3)%M;
}	
void pushdown(int p)
{
	if (tr[p].tag_3)
	{
		tr[lc].sum_1 = ((tr[lc].r - tr[lc].l + 1) * tr[p].tag_3)%M;
		tr[lc].sum_2 = ((tr[lc].r - tr[lc].l + 1) * tr[p].tag_3%M * tr[p].tag_3)%M;
		tr[lc].sum_3 = ((tr[lc].r - tr[lc].l + 1) * tr[p].tag_3%M * tr[p].tag_3%M *tr[p].tag_3 )% M;
		tr[rc].sum_1 = ((tr[rc].r - tr[rc].l + 1) * tr[p].tag_3 )% M;
		tr[rc].sum_2 = ((tr[rc].r - tr[rc].l + 1) * tr[p].tag_3%M * tr[p].tag_3) % M;
		tr[rc].sum_3 = ((tr[rc].r - tr[rc].l + 1) * tr[p].tag_3%M * tr[p].tag_3%M * tr[p].tag_3%M ) % M;
		tr[lc].tag_3 = tr[p].tag_3;
		tr[rc].tag_3 = tr[p].tag_3;
		tr[lc].tag_2 = 1, tr[lc].tag_1 = 0;
		tr[rc].tag_2 = 1, tr[rc].tag_1 = 0;
		tr[p].tag_3 = 0;
	}
	if (tr[p].tag_2!=1)
	{
		tr[lc].sum_1 = (tr[lc].sum_1 * (tr[p].tag_2 % M)) % M;
		tr[lc].sum_2 = (tr[lc].sum_2 * (tr[p].tag_2 % M) * (tr[p].tag_2 % M)) % M;
		tr[lc].sum_3 = ((tr[lc].sum_3 * (tr[p].tag_2 % M)) * (tr[p].tag_2 % M) * (tr[p].tag_2 % M)) % M;
		tr[rc].sum_1 = (tr[rc].sum_1 * (tr[p].tag_2 % M)) % M;
		tr[rc].sum_2 = (tr[rc].sum_2 * (tr[p].tag_2 % M) * (tr[p].tag_2 % M)) % M;
		tr[rc].sum_3 = ((tr[rc].sum_3 * (tr[p].tag_2 % M)) * (tr[p].tag_2 % M) * (tr[p].tag_2 % M)) % M;
		tr[lc].tag_2 = tr[lc].tag_2 * tr[p].tag_2 % M;
		tr[lc].tag_1 = tr[lc].tag_1 * tr[p].tag_2 % M;
		tr[rc].tag_2 = tr[rc].tag_2 * tr[p].tag_2 % M;
		tr[rc].tag_1 = tr[rc].tag_1 * tr[p].tag_2 % M;
		tr[p].tag_2 = 1;
	}
	if (tr[p].tag_1)
	{
		LL a = tr[lc].sum_1, b = tr[lc].sum_2, c = tr[lc].sum_3;
		tr[lc].sum_1 = (tr[lc].sum_1 + (tr[lc].r - tr[lc].l + 1) * tr[p].tag_1) % M;
		tr[lc].sum_2 = (tr[lc].sum_2 + ((tr[lc].r - tr[lc].l + 1) * tr[p].tag_1 * tr[p].tag_1 + 2 * tr[p].tag_1 * a)) % M;
		tr[lc].sum_3 = (tr[lc].sum_3 + 3 * tr[p].tag_1 * b + 3 * tr[p].tag_1 % M * tr[p].tag_1 % M * a % M + (tr[lc].r - tr[lc].l + 1) * tr[p].tag_1 % M * tr[p].tag_1 % M * tr[p].tag_1 % M) % M;
		a = tr[rc].sum_1, b = tr[rc].sum_2, c = tr[rc].sum_3;
		tr[rc].sum_1 = (tr[rc].sum_1 + (tr[rc].r - tr[rc].l + 1) * tr[p].tag_1) % M;
		tr[rc].sum_2 = (tr[rc].sum_2 + ((tr[rc].r - tr[rc].l + 1) * tr[p].tag_1 % M * tr[p].tag_1 % M + 2 * tr[p].tag_1 * a)) % M;
		tr[rc].sum_3 = (tr[rc].sum_3 + 3 * tr[p].tag_1 * b % M + 3 * tr[p].tag_1 % M * tr[p].tag_1 % M * a % M + (tr[rc].r - tr[rc].l + 1) * tr[p].tag_1 % M * tr[p].tag_1 % M * tr[p].tag_1 % M) % M;
		tr[lc].tag_1 += tr[p].tag_1;
		tr[rc].tag_1 += tr[p].tag_1;
		tr[p].tag_1 = 0;
	}
}
void build(int p, int l, int r)
{
	tr[p] = { l,r,0,0,0,0,1,0};
	if (l == r)return;
	int m = l + r >> 1;
	build(lc, l, m);
	build(rc, m + 1, r);
	pushup(p);
}
void update(int p, int x, int y, int c,LL k)
{		

	if (c == 1)
	{
		if (x <= tr[p].l && tr[p].r <= y)
		{
			LL a = tr[p].sum_1, b = tr[p].sum_2;
			tr[p].sum_1 = (tr[p].sum_1 + (tr[p].r - tr[p].l + 1) * k) % M;
			tr[p].sum_2 = (tr[p].sum_2 + ((tr[p].r - tr[p].l + 1) * k%M * k%M + 2 * k%M * a%M)) % M;
			tr[p].sum_3 = (tr[p].sum_3 + 3 * k%M * b%M + 3 * k%M * k%M * a %M+ (tr[p].r - tr[p].l + 1) * k%M * k%M * k%M) % M;
			tr[p].tag_1 = (tr[p].tag_1+k)%M;
			return;
		}
	}
	else if (c == 2)
	{
		if (x <= tr[p].l && tr[p].r <= y)
		{
			tr[p].sum_1 = (tr[p].sum_1 * k) % M;
			tr[p].sum_2 = (tr[p].sum_2 * k % M * k % M);
			tr[p].sum_3 = ((tr[p].sum_3 * k % M) * k % M * k % M);
			tr[p].tag_2 = tr[p].tag_2 * k % M;
			tr[p].tag_1 = tr[p].tag_1 * k % M;
			return;
		}
	}
	else
	{
		if (x <= tr[p].l && tr[p].r <= y)
		{
			tr[p].sum_1 = (tr[p].r - tr[p].l + 1) * k % M;
			tr[p].sum_2 = ((tr[p].r - tr[p].l + 1) * k%M) % M * k % M;
			tr[p].sum_3 = ((tr[p].r - tr[p].l + 1) * k%M) * ((k * k%M)) % M;
			tr[p].tag_3 = k;
			tr[p].tag_1 = 0;
			tr[p].tag_2 = 1;
			return;
		}
	}
	pushdown(p);
	int m = tr[p].l + tr[p].r >> 1;
	if (x <= m)update(lc, x, y, c,k);
	if (y > m)update(rc, x, y, c, k);
	pushup(p);
}
LL query(int p, int x, int y, int c)
{
	if (x <= tr[p].l && tr[p].r <= y)
	{
		if (c == 1)return tr[p].sum_1;
		else if (c == 2)return tr[p].sum_2;
		else return tr[p].sum_3;
	}
	pushdown(p);
	LL sum = 0;
	int m = tr[p].r + tr[p].l >> 1;
	if (x <= m)sum += query(lc, x, y, c);
	if (y > m)sum += query(rc, x, y, c);
	return sum % M;
}
int main()
{
	while (scanf("%d%d",&n,&m)&&n)
	{
		build(1, 1, n);
		while (m--)
		{
			int op, x, y, c;
			scanf("%d%d%d%d", &op, &x, &y, &c);
			if (op == 1)
			{
				update(1, x, y, 1,c%M);
			}
			else if (op == 2)
			{
				update(1, x, y, 2,c%M);
			}
			else if (op == 3)
			{
				update(1, x, y, 3,c%M);
			}
			else
			{
				printf("%lld\n", query(1, x, y, c));
			}
		}
	}
	return 0;
}

标签：hdu,lc,int,线段,tr,tag,rc,4578,sum
From： https://www.cnblogs.com/wyh344866/p/17284429.html

相关文章

  • 线段树模板复习
    建树voidbuild(intl,intr,intrt){ if(l==r) { t[rt]=a[l]; return; } intmid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,(rt<<1)|1); t[rt]=t[rt<<1]+t[(rt<<1)|1];}标记下传voidpushdown(intl,intr,intrt){ if(lazy......
  • Codeforces Gym 103931F - Forest of Magic（时间轴分块+线段树合并）
    一个巨烦的时间轴分块做法，有点类似于P2137Gty的妹子树先考虑静态的情况。看上去就一脸线段树合并对吧？一次修改的操作对一个点\(x\)贡献可以写成\(k·dep_x+b\)的形式，开两棵线段树合并维护一次项和零次项系数即可。由于静态问题可做，因此考虑时间轴分块。设阈值\(B\)，每\(B......
  • HDU 3328 Flipper 栈的应用
    FlipperTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):521    AcceptedSubmission(s):334ProblemDescriptionLittleBobbyRoberts(sonofBigBob,ofProblemG)playsthissolitairememory......
  • CAD如何测量连续线段长度？CAD测量连续线段长度步骤
    在CAD绘图过程中，经常会绘制一些连续的线段，如果想要知道这些连续线段长度的话，该怎么操作吗？CAD如何测量连续线段长度？下面小编就以浩辰CAD软件为例来给大家分享一下CAD测量连续线段长度的具体操作步骤吧！CAD测量连续线段长度步骤：浩辰CAD软件中已经考虑到了这种需求，在CAD测量命令（DIST......
  • hdu3595 GG and MM Every SG博弈
    这是一道很神奇的题，神奇的地方在于全网这个模型只有这题什么是EverySG？不同于普通的ICG，它由多个游戏同时进行，且必须同时进行比如这道题，要求先手一次对所有石头堆都要操作显然对于单独的每种情况，我们都可以求出这是必败态还是必胜态现在摆在我们眼前的就有一堆游戏，对于每个游......
  • hdu3980 Paint Chain SG函数+SG定理+记忆化搜索
    liyishui今天学习博弈，因为liyishui今天写树链剖分写得有点理智--题意：有一个圆，上面有n个豆子，每次要挑出连续m个没染色的豆子进行染色，不能移动时输掉游戏问先手必胜还是后手必胜，其中n、m<=1000题解：会很朴素地想到如果第一个人拿走了m个，那么剩下的就是一条链的问题。所以可以先......
  • CF1295E Permutation Separation 题解 线段树优化dp
    题目链接：https://codeforces.com/problemset/problem/1295/E题目大意：将排列\(p_1,p_2,\ldots,p_n\)先分成\(p_1,\ldots,p_k\)与\(p_{k+1},\ldots,p_n\)两个......
  • 确定比赛名次 HDU - 1285 （拓扑排序）
    题意：有N个比赛队（1≤N≤500），编号依次为1，2，3，...，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比......
  • Transformation HDU - 4578
    题目链接\(1\)题目链接\(2\)题解设一个区间的和、平方和、立方和分别是\(sum_0,sum_1,sum_2\)对于\(add\)操作，推推公式可知\(\begin{cases}newsum_2=sum_2+val^3......
  • [USACO08FEB]Hotel G 线段树区间合并|维护最长的连续1
    这个还是看代码，比讲的清楚#include<bits/stdc++.h>#definefastioios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)#definels(rt<<1)#definers(rt<<1|1......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99