主体段树，要注意，因为有set和add操作，当慵懒的标志下推。递归优先set，后复发add，每次运行set行动add马克清0
WA了好几次是由于计算那一段的时候出问题了，可笑的是我对着模板找了一个多小时的错。
#include #include #include #include #include #include using namespace std; #define lson pos << 1 #define rson pos << 1|1 typedef unsigned long long ULL; typedef long long LL; const int maxn = 1111111; const int INF = 1 << 30; struct Node{int left,right;int max_value,min_value,sum_value;int col;int col2; }tr[maxn << 2]; struct Ans{int min_value;int max_value;int sum_value;Ans(int a = INF,int b = 0,int c = 0):min_value(a),max_value(b),sum_value(c){}; }; int n,m,k; void pushdown(int pos){if(tr[pos].col){int len1 = tr[lson].right - tr[lson].left + 1;int len2 = tr[rson].right - tr[rson].left + 1;tr[lson].sum_value += (tr[pos].col * len1);tr[lson].max_value += tr[pos].col;tr[lson].min_value += tr[pos].col;tr[rson].sum_value += (tr[pos].col * len2);tr[rson].max_value += tr[pos].col;tr[rson].min_value += tr[pos].col;tr[lson].col += tr[pos].col;tr[rson].col += tr[pos].col;tr[pos].col = 0;}return ; } void pushdown2(int pos){if(tr[pos].col2 >= 0){int len1 = tr[lson].right - tr[lson].left + 1;int len2 = tr[rson].right - tr[rson].left + 1;tr[lson].sum_value = (tr[pos].col2 * len1);tr[lson].max_value = tr[pos].col2;tr[lson].min_value = tr[pos].col2;tr[rson].sum_value = (tr[pos].col2 * len2);tr[rson].max_value = tr[pos].col2;tr[rson].min_value = tr[pos].col2;tr[lson].col2 = tr[pos].col2; tr[lson].col = 0; //set递推须要清空求和tr[rson].col2 = tr[pos].col2; tr[rson].col = 0;tr[pos].col2 = -1;}return ; } void pushup(int pos){tr[pos].sum_value = tr[lson].sum_value + tr[rson].sum_value;tr[pos].max_value = max(tr[lson].max_value,tr[rson].max_value);tr[pos].min_value = min(tr[lson].min_value,tr[rson].min_value);return ; } void BuildTree(int L,int R,int pos){tr[pos].left = L; tr[pos].right = R; tr[pos].col = 0;tr[pos].col2 = -1;tr[pos].max_value = 0; tr[pos].min_value = 0; tr[pos].sum_value = 0;if(L == R) return ;int m = (L + R) >> 1;BuildTree(L,m,lson);BuildTree(m + 1,R,rson);return ; } void TreeAdd(int l,int r,int add,int pos){if(l <= tr[pos].left && tr[pos].right <= r){int len = tr[pos].right - tr[pos].left + 1;tr[pos].max_value += add; tr[pos].min_value += add;tr[pos].sum_value += (add * len); tr[pos].col += add;return ;}pushdown2(pos);pushdown(pos);int m = (tr[pos].left + tr[pos].right) >> 1;if(l <= m)TreeAdd(l,r,add,lson);if(r > m)TreeAdd(l,r,add,rson);pushup(pos); } void TreeSet(int l,int r,int value,int pos){if(l <= tr[pos].left && tr[pos].right <= r){int len = tr[pos].right - tr[pos].left + 1;tr[pos].max_value = value; tr[pos].min_value = value;tr[pos].sum_value = (value * len); tr[pos].col2 = value;tr[pos].col = 0;return ;}pushdown2(pos);pushdown(pos);int m = (tr[pos].left + tr[pos].right) >> 1;if(l <= m)TreeSet(l,r,value,lson);if(r > m)TreeSet(l,r,value,rson);pushup(pos); } Ans Query(int l,int r,int pos){if(l <= tr[pos].left && tr[pos].right <= r){return Ans(tr[pos].min_value,tr[pos].max_value,tr[pos].sum_value);}pushdown2(pos);pushdown(pos);int m = (tr[pos].left + tr[pos].right) >> 1;Ans a,b;if(l <= m)a = Query(l,r,lson);if(r > m)b = Query(l,r,rson);pushup(pos);return Ans(min(a.min_value,b.min_value),max(a.max_value,b.max_value),a.sum_value + b.sum_value); } int main(){while(scanf("%d%d%d",&n,&m,&k) != EOF){BuildTree(1,n * m,1);while(k--){int t;scanf("%d",&t);if(t == 1){int x1,y1,x2,y2,v;//addscanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);for(int i = x1 ; i <= x2 ; i++){int l = (i - 1) * m + y1;int r = (i - 1) * m + y2;TreeAdd(l,r,v,1);}}else if(t == 2){int x1,y1,x2,y2,v;//addscanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);for(int i = x1 ; i <= x2 ; i++){int l = (i - 1) * m + y1;int r = (i - 1) * m + y2;TreeSet(l,r,v,1);}}else if(t == 3){int x1,y1,x2,y2;Ans t;int MAX = 0,MIN = INF,SUM = 0;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for(int i = x1 ; i <= x2 ; i++){int l = (i - 1) * m + y1;int r = (i - 1) * m + y2;t = Query(l,r,1);SUM += t.sum_value;MAX = max(MAX,t.max_value);MIN = min(MIN,t.min_value);}printf("%d %d %d ",SUM,MIN,MAX);}}}return 0; }
版权声明：本文博客原创文章，博客，未经同意，不得转载。
转载于:https://www.cnblogs.com/gcczhongduan/p/4713382.html
输入格式 输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格 输出格式 对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结 果，每个答案（数字）占...
【传送门：BZOJ4491】 简要题意： 给出一个长度为n的序列，m个操作，每个操作输入x，y，求出第x个数到第y个数的最长子串，保证这个最长子串是不上升或不下降子串 题解： 线段树 因为不上升或不下降嘛，就差分一下呗 每一段区间维护： d表示最多连续的非正数的个数，u表示最多连续的非负数的个数 ld表示左端点...
但是对于表格要注意，在
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3598 数位DP...东看西看：http://www.cnblogs.com/Artanis/p/3751644.html https://www.cnblogs.com/MashiroSky/p/6399...
翻页器
在src/main/resources/springmvc-servlet.xml中加入
本篇仅仅是一个记录 MergeOperator 的使用方式。 Rocksdb 使用MergeOperator 来代替Update 场景中的读改写操作，即用户的一个Update 操作需要调用rocksdb的 Get + Put 接口才能完成。 而这种情况下会引入一些额外的读写放大，对于支持SQL这种update 频繁的场景来说实在是不划...
看了很多人写的好几个去重方法，我在这里精简组合下，适用于已排序与未排序的数组。 废话不多说，上代码。