生活随笔
收集整理的这篇文章主要介绍了
教主的魔法
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
传送门：https://www.luogu.org/problemnew/show/P2801
这道题当时在考场上时间不够了w，没有来得及码线段树，也没有去敲分块w，只是去搞个n^2暴力。。。
结果，悲哀的事情是，我的快读写错了，然后样例还过了。。。。。自己造的数据还是两位数的都读进去了w。。。
然后考完试之后的我依旧不想写分块or线段树。。。。
于是乎，嘿嘿嘿：
我们看一下数据范围，Q ≤ 3000，一开始的身高 ≤ 1000，还不强制在线。
这意味着什么？
这意味着我们可以搞一些事情。
由于我们的询问只有3000个，那么这个序列就被这询问的3000个左端点和3000个右端点分成了6000段（还是6001段。。。。。这不重要）。
然后对于每一段我们用s[i][j]记录第i段权值 ≥ j 的有多少个.
对于每一段区间都枚举一遍所有的询问，修改肯定是整段区间一起修改，打个标记就可以了，查询的时候把询问减掉标记查一下权值。
时间复杂度是O(2Q(Q+1000))。
#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#define LL long long
#define inf 1000000009
#define N 1000000
using namespace std;
inline int read() {int s = 0,w = 1;char ch = getchar();while(ch < '0' || ch > '9') {if(ch == '-')w = -1;ch = getchar();}while(ch >= '0' && ch <= '9') {s = s * 10 + ch - '0';ch = getchar();}return s * w;
}
void file() {//srand(time(NULL)+rand());freopen("qwq.in","r",stdin);freopen("qwq.out","w",stdout);
}
int n,Q,k,a[N],f[N],len,m,s[6005][1005],tag[N],ans[N],res;
struct query {int opt,l,r,v,id;
} e[N];
void init() {n = read(),Q = read();for(int i = 1; i <= n; i++) {a[i] = read();}for(int i = 1,c; i <= Q; i++) {c = 0;while(c != 'M' && c != 'A')c = getchar();e[i].opt = (c == 'A');e[i].l = read();e[i].r = read();e[i].v = read();f[++res] = e[i].l;f[++res] = e[i].r + 1;if(c == 'A') {e[i].id = ++k;}}return ;
}
void solve() {sort(f + 1,f + res + 1);m = unique(f + 1,f + res + 1) - f - 1;f[m + 1] = n + 1;for(int i = 1; i <= Q; i++) {e[i].l = lower_bound(f + 1,f + m + 1,e[i].l) - f;e[i].r = upper_bound(f + 1,f + m + 1,e[i].r) - f - 1;}for(int i = 1; i <= m; i++) {for(int j = f[i]; j < f[i + 1]; j++) {s[i][a[j]]++;}for(int j = 1000; j; j--) {s[i][j] += s[i][j + 1];}}for(int i = 1; i <= m; i++) {for(int j = 1; j <= Q; j++) {if(e[j].l <= i && i <= e[j].r) {if(!e[j].opt) tag[i] += e[j].v;else {if(e[j].v - tag[i] <= 0) ans[e[j].id] += f[i + 1] - f[i];else if(e[j].v - tag[i] <= 1000) ans[e[j].id] += s[i][e[j].v - tag[i]];}}}}for(int i = 1; i <= k; i++) {printf("%d\n",ans[i]);}return ;
}
int main() {init();solve();return 0;
}
转载于:https://www.cnblogs.com/excellent-zzy/p/10992031.html
总结
以上是生活随笔为你收集整理的教主的魔法的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
