这道题也有点新意，就是须要记录最小值段和最大值段，然后成段更新这个段，而不用没点去更新，达到提快速度的目的。
本题过的人非常少，由于大部分都超时了，我严格依照线段树的方法去写。一開始竟然也超时。
然后修补了两个地方就过了，详细改动的地方请參看程序。
知道最大值段和最小值段，然后修补一下就能过了。不是特别难的题目。
#include
#include
#include
using namespace std;
const int SIZE = 200002;
const int TREESIZE = SIZE + (SIZE<>1);
build(l, m, lChild(rt));
build(m+1, r, rChild(rt));
}
inline void pushUp(int rt)
{
smallest[rt] = min(smallest[lChild(rt)], smallest[rChild(rt)]);
largest[rt] = max(largest[lChild(rt)], largest[rChild(rt)]);
}
inline void pushDown(int rt)
{
if(segTree[rt])
{
int l = lChild(rt), r = rChild(rt);
largest[l] += segTree[rt];
largest[r] += segTree[rt];
smallest[l] += segTree[rt];
smallest[r] += segTree[rt];
segTree[l] += segTree[rt];
segTree[r] += segTree[rt];
segTree[rt] = 0;
}
}
void update(int L, int R, int val, int l, int r, int rt)
{
if (L = P)
{
smallest[rt] += val<>1);
if (L >1);
printTree(l, m, lChild(rt));
printTree(m+1, r, rChild(rt));
}
int main()
{
int a, b, c;
while (scanf("%d %d %d", &N, &M, &P) != EOF)
{
build(1, N, 1);
//memset(largest, 0, sizeof(largest)); 这样写反而超时
//memset(smallest, 0, sizeof(smallest));
//memset(segTree, 0, sizeof(segTree));
while (M--)
{
scanf("%d %d %d", &a, &b, &c);
update(a, b, c, 1, N, 1);
}
printTree(1, N, 1);
}
return 0;
}
Original: https://www.cnblogs.com/hrhguanli/p/5109866.html
Author: hrhguanli
Title: HDU 4107 Gangster Segment Tree线段树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/546052/
转载文章受原作者版权保护。转载请注明原作者出处！