站酷网官网进入,wordpress中文主题 wp-cms,绍兴做网站服务,天睦和生态建设有限公司网站传送门(权限题) 题目分析 题意为#xff1a;给定一个数列#xff0c;修改和查询两种操作#xff0c;修改每次给定一个区间#xff0c;区间的所有元素都加上一个给定值#xff0c;查询询问一段区间的数权值大于等于给定值的数有多少个。 首先对原序列分块#xff0c;然后将…传送门(权限题) 题目分析 题意为给定一个数列修改和查询两种操作修改每次给定一个区间区间的所有元素都加上一个给定值查询询问一段区间的数权值大于等于给定值的数有多少个。 首先对原序列分块然后将分块后的数组每个块内的数字进行排序这样查询时就可以暴力枚举散块并二分枚举每个整块。对于修改对于整块部分只需修改tag然后暴力修改散块的原序列值然后对散块元素所在块进行重排序即可。 code 3048 ms #includeiostream
#includecstdio
#includecstdlib
#includecstring
#includecmath
#includealgorithm
#includevector
using namespace std;const int N 1e6 5;
int n, Q, h[N], H[N], tag[N], S, blo;
#define bug(x) cout#x:xendl
inline int read(){int i 0, f 1; char ch getchar();for(; (ch 0 || ch 9) ch ! -; ch getchar());if(ch -) f -1, ch getchar();for(; ch 0 ch 9; ch getchar())i (i 3) (i 1) (ch - 0);return i * f;
}inline void wr(int x){if(x 0) putchar(-),x -x;if(x 9) wr(x / 10);putchar(x % 10 0);
}inline void add(int x, int y, int v){if(y - x 1 2 * S){for(int i x; i y; i)h[i] v;}int Bx x / S (x % S ? 1 : 0), By y / S (y % S ? 1 : 0);int L Bx 1, R By - 1;if(x (Bx - 1) * S 1) L--;if(y min(n, By * S)) R;int ans 0;for(int i x; i (L - 1) * S; i)h[i] v;int l (Bx - 1) * S 1, r min(n, Bx * S);for(int i l; i r; i)H[i] h[i];sort(H l, H r 1);for(int i min(n, R * S) 1; i y; i)h[i] v;l (By - 1) * S 1, r min(n, By * S);for(int i l; i r; i)H[i] h[i];sort(H l, H r 1);for(int i L; i R; i)tag[i] v;
}inline int query(int x, int y, int v){int ans 0;if(y - x 1 2 * S){for(int i x; i y; i)if(h[i] tag[i / S (i % S ? 1 : 0)] v) ans;return ans;}int Bx x / S (x % S ? 1 : 0), By y / S (y % S ? 1 : 0);
// bug(Bx), bug(By);int L Bx 1, R By - 1;if(x (Bx - 1) * S 1) L--;if(y min(n, By * S)) R;
// bug(L), bug(R);for(int i x; i (L - 1) * S; i)if(h[i] tag[Bx] v) ans;for(int i min(n, R * S) 1; i y; i)if(h[i] tag[By] v) ans;for(int i L; i R; i){int l (i - 1) * S 1, r min(n, i * S), len r - l 1;int tmp lower_bound(H l, H r 1, v - tag[i]) - (H l - 1);ans len - (tmp - 1);}return ans;
}int main(){n read(), Q read(), S sqrt(n), blo n / S (n % S ? 1 : 0);
// bug(S);for(int i 1; i n; i) h[i] H[i] read();for(int i 1; i blo; i){int l (i - 1) * S 1, r min(i * S, n);sort(H l, H r 1);}for(int i 1; i Q; i){char opt[5]; scanf(%s, opt 1);if(opt[1] M){int l read(), r read(), w read();add(l, r, w);}else if(opt[1] A){int l read(), r read(), c read();wr(query(l, r, c)), putchar(\n);}}return 0;
} 转载于:https://www.cnblogs.com/CzYoL/p/7396352.html
