SDUT2880 Devour Magic 线段树(set+add标记)

2024-08-28 00:38

本文主要是介绍SDUT2880 Devour Magic 线段树(set+add标记),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Devour Magic

Time Limit: 2000ms   Memory limit: 65536K  有疑问?点这里^_^

题目描述

In Warcraft III, Destroyer is a large flying unit that must consume magic to sustain its mana. Breaking free of the obsidian stone that holds them, these monstrous creatures roar into battle, swallowing magic to feed their insatiable hunger as they move between battles and rain destruction down upon their foes. Has Spell Immunity. Attacks land and air units.
The core skill of the Destroyer is so called Devour Magic, it takes all mana from all units in a area and gives it to the Destroyer.
Now to simplify the problem, assume you have n units in a line, all unit start with 0 mana and can increase to infinity maximum mana. All unit except the Destroyer have mana regeneration 1 in per unit time.
The Destroyer have m instructions t l r, it means, in time t, the Destroyer use Devour Magic on unit from l to r. We give you all m instructions in time order, count how many mana the Destroyer have devour altogether.

输入

The first line contains one integer T, indicating the test case. For each test case, the first contains two integer n, m(1 ≤ n, m ≤ 10^5). The the next m line each line contains a instruction t l r.(1 ≤ t ≤ 10^5, 1 ≤ l ≤ r ≤ n)

输出

For each test case, output the conrespornding result.

示例输入

1
10 5
1 1 10
2 3 10
3 5 10
4 7 10
5 9 10

示例输出

30

题目链接:http://www.sdutacm.org/sdutoj/problem.php?action=showproblem&problemid=2880

线段树:set+add操作,不错的题。

注意一下两者的顺序,set优先,add在后,这个都应该能理解。

/*
线段树
结论:只要是set的,就是直接赋值的;只要是add的,就是在原基础上加的;set时把add置0
还有就是时刻更新sum值,使其保持正确.
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;const int maxn=100000+10;
ll sum[maxn*4],add[maxn*4],set[maxn*4];void pushUp(int k){sum[k]=sum[k*2]+sum[k*2+1];
}void pushDown(int k,int l,int r){int lc=k*2,rc=k*2+1,m=(l+r)/2;if(set[k]!=-1){add[lc]=add[rc]=0;      //这里被赋值,那么子树的add就没用了set[lc]=set[rc]=set[k];sum[lc]=set[k]*(m-l+1); //这里的sum就是直接赋值,因为之前的值不复存在,而是用现在的新的set值计算sum[rc]=set[k]*(r-m);set[k]=-1;}if(add[k]){add[lc]+=add[k];add[rc]+=add[k];sum[lc]+=add[k]*(m-l+1);    //处理add时,sum就不能直接赋值,而是在原来的基础上加sum[rc]+=add[k]*(r-m);add[k]=0;}
}void Set(int a,int b,ll v,int k,int l,int r){if(a<=l && r<=b){set[k]=v;add[k]=0;sum[k]=v*(r-l+1);return ; //注意这里有add[k]=0!!!!!!!!!!!!!!!!!!}pushDown(k,l,r);int m=(l+r)/2;if(a<=m)Set(a,b,v,k*2,l,m);if(b>m)Set(a,b,v,k*2+1,m+1,r);pushUp(k);
}void Add(int a,int b,ll v,int k,int l,int r){if(a<=l && r<=b){add[k]+=v;sum[k]+=v*(r-l+1);return ;}pushDown(k,l,r);int m=(l+r)/2;if(a<=m)Add(a,b,v,k*2,l,m);if(b>m)Add(a,b,v,k*2+1,m+1,r);pushUp(k);
}ll ask(int a,int b,int k,int l,int r){if(a<=l && r<=b){return sum[k];}pushDown(k,l,r);int m=(l+r)/2;ll res=0;if(a<=m)res+=ask(a,b,k*2,l,m);if(b>m)res+=ask(a,b,k*2+1,m+1,r);pushUp(k);return res;
}int main()
{int i,T,n,m,a,b,t;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);memset(add,0,sizeof(add));Set(1,n,(ll)0,1,1,n);       //set[1]=0是不对的。。。。。ll res=0;t=0;while(m--){int t1;scanf("%d%d%d",&t1,&a,&b);Add(1,n,(ll)t1-t,1,1,n);res+=ask(a,b,1,1,n);Set(a,b,(ll)0,1,1,n);t=t1;}printf("%lld\n",res);}return 0;
}


这篇关于SDUT2880 Devour Magic 线段树(set+add标记)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1113239

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

圆与线段的交点

poj 3819  给出一条线段的两个端点,再给出n个圆,求出这条线段被所有圆覆盖的部分占了整条线段的百分比。 圆与线段的交点 : 向量AB 的参数方程  P = A + t * (B - A)      0<=t<=1 ; 将点带入圆的方程即可。  注意: 有交点 0 <= t <= 1 ; 此题求覆盖的部分。 则 若求得 t  满足 ; double ask(d