能上国外网站的dns,网络营销服务外包,深圳网站建设机构,电脑优化系统的软件哪个好https://oj.gxu.edu.cn/contest/7/problem/D 描述 有一个所有元素皆为0的数组A#xff0c;有两种操作#xff1a; 1 l r x表示将A区间[l,r]内所有数加上x#xff1b; 2 l r表示将A区间[l,r]内从左往右数第i个数加上i#xff1b; 给出m个操作#xff0c;请输出操作结束后A中…https://oj.gxu.edu.cn/contest/7/problem/D 描述 有一个所有元素皆为0的数组A有两种操作 1 l r x表示将A区间[l,r]内所有数加上x 2 l r表示将A区间[l,r]内从左往右数第i个数加上i 给出m个操作请输出操作结束后A中的最大值。 输入 第一行一个整数m表示操作的个数 接下来有m行表示操作的内容具体格式与题目中一致 0m10^6 1lr10^6 0x10^9 输出 输出一个整数表示所有操作之后A中的最大值 思路差分难点在于三角形怎么处理。 其实也不难计算一下有几个三角形在哪里出现又消失就可以了。当三角形消失的时候解除掉三角形对当前的影响就足够了。 首先对差分求前缀和可以复原原数组这个简单。 那么对三角形数量差分求前缀和可以复原每个区间的三角形的数量。 发现每一个三角形会使得前缀和增加1解除这个三角形的时候就要把它的贡献一并解除掉。显然贡献就是区间长。 所以这个数据结构可以叫做“LD三角形区间修改前缀和” #includebits/stdc.h
using namespace std;
typedef long long ll;inline ll read() {ll x 0;bool f 0;char c;do {c getchar();if(c -)f 1;} while(c 0 || c 9);do {x (x 3) (x 1) c - 0;c getchar();} while(c 0 c 9);return f ? -x : x;
}inline void _write(ll x) {if(x 9)_write(x / 10);putchar(x % 10 0);
}inline void write(ll x) {if(x 0) {putchar(-);x -x;}_write(x);putchar(\n);
}/*--- ---*/const int MAXM 1000000;
ll df1[MAXM5];
int df2[MAXM5];inline void update(int l, int r, ll v) {df1[l]v;df1[r1]-v;
}inline void update2(int l, int r) {df2[l]1;df2[r1]-1;df1[r1]-(r-l1);
}inline ll calc() {ll ans0;int curd0;ll curs0;for(int i1;iMAXM;i){curddf2[i];curscurd;cursdf1[i];if(cursans)anscurs;}return ans;
}int main() {
#ifdef Yinkufreopen(Yinku.in, r, stdin);//freopen(Yinku.out,w,stdout);
#endif // Yinkuint mread();while(m--){int opread(),lread(),rread();if(op1){int xread();update(l,r,x);}else{update2(l,r);}}write(calc());
} 要是少一个数量级其实可以线段树 #includebits/stdc.h
using namespace std;
typedef long long ll;inline ll read() {ll x 0;//int f 0;char c;do {c getchar();/*if(c -)f 1;*/} while(c 0 || c 9);do {x (x 3) (x 1) c - 0;c getchar();} while(c 0 c 9);//return f ? -x : x;return x;
}inline void _write(int x) {if(x 9)_write(x / 10);putchar(x % 10 0);
}inline void write(int x) {if(x 0) {putchar(-);x -x;}_write(x);putchar(\n);
}/*--- ---*/const int MAXM 1000000;
ll a[MAXM 5];
ll lazy[(MAXM 2) 5];
int lazy2[(MAXM 2) 5];inline void push_down(int o, int l, int r) {if(lazy[o] || lazy2[o]) {lazy[o 1] lazy[o];lazy[o 1 | 1] lazy[o];int m (l r) 1;lazy2[o 1] lazy2[o];lazy2[o 1 | 1] lazy2[o];lazy[o 1 | 1] (m - l 1) * lazy2[o];lazy[o] 0;lazy2[o] 0;}
}void build() {memset(a, 0, sizeof(a));memset(lazy, 0, sizeof(lazy));memset(lazy2, 0, sizeof(lazy2));
}void update(int o, int l, int r, int a, int b, ll v) {if(a l r b) {lazy[o] v;return;} else {push_down(o, l, r);int m (l r) 1;if(a m)update(o 1, l, m, a, b, v);if(b m 1)update(o 1 | 1, m 1, r, a, b, v);}
}void update2(int o, int l, int r, int a, int b, int h) {//这个区间底下包含一个高为h的矩形然后上面是一个三角形最左侧恰好有h1个方块if(a l r b) {lazy[o] h;lazy2[o];return;} else {push_down(o, l, r);int m (l r) 1;if(a m)update2(o 1, l, m, a, b, h);//左侧底下方块是一样的if(b m 1)update2(o 1 | 1, m 1, r, a, b, h m - a 1);//右侧多m-a1个方块}
}void all_pushdown(int o, int l, int r) {if(l r) {a[l] lazy[o] lazy2[o];} else {push_down(o, l, r);int m (l r) 1;all_pushdown(o 1, l, m);all_pushdown(o 1 | 1, m 1, r);}
}int main() {
#ifdef Yinkufreopen(Yinku.in, r, stdin);//freopen(Yinku.out,w,stdout);
#endif // Yinku//sieve();build();int mread();while(m--){int opread(),lread(),rread();if(op1){int xread();update(1,1,1000000,l,r,x);}else{update2(1,1,1000000,l,r,0);}}all_pushdown(1,1,1000000);ll maxansa[1];for(int i2;i1000000;i){if(a[i]maxans)maxansa[i];}printf(%lld\n,maxans);
} 转载于:https://www.cnblogs.com/Yinku/p/11073411.html
