[BZOJ3343]教主的魔法
试题描述
输入
输出
输入示例
5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4
输出示例
2 3
数据规模及约定
对30%的数据，N≤1000，Q≤1000。
对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。
题解
这题询问较少，但 N 比较大，可以往 O(Q√n) 复杂度的算法这个方向去想，况且这个题目用数据结构很难维护，所以就会想到分块。
想到分块之后就很简单了，每个块内部排一遍序，整块查询时可以二分，边上两块就可以暴力处理了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); }
return x * f;
}
#define maxn 1000010
#define maxb 1010
int n, q, A[maxn], Blo[maxn], st[maxb], en[maxb], addv[maxb], cb, pos[maxn];
void update(int l, int r, int val) {
int bl = pos[l], br = pos[r];
if(br - bl < 2) {
for(int i = st[bl]; i <= en[br]; i++) A[i] += addv[pos[i]]; addv[bl] = addv[br] = 0;
for(int i = l; i <= r; i++) A[i] += val;
for(int i = st[bl]; i <= en[br]; i++) Blo[i] = A[i];
sort(Blo + st[bl], Blo + en[bl] + 1);
sort(Blo + st[br], Blo + en[br] + 1);
return ;
}
for(int i = st[bl]; i <= en[bl]; i++) A[i] += addv[bl]; addv[bl] = 0;
for(int i = st[br]; i <= en[br]; i++) A[i] += addv[br]; addv[br] = 0;
for(int i = l; i <= en[bl]; i++) A[i] += val;
for(int i = st[br]; i <= r; i++) A[i] += val;
for(int i = st[bl]; i <= en[bl]; i++) Blo[i] = A[i]; sort(Blo + st[bl], Blo + en[bl] + 1);
for(int i = st[br]; i <= en[br]; i++) Blo[i] = A[i]; sort(Blo + st[br], Blo + en[br] + 1);
for(int i = bl + 1; i <= br - 1; i++) addv[i] += val;
return ;
}
int query(int l, int r, int val) {
int bl = pos[l], br = pos[r], ans = 0;
if(br - bl < 2) {
for(int i = st[bl]; i <= en[br]; i++) A[i] += addv[pos[i]], Blo[i] += addv[pos[i]];
addv[bl] = addv[br] = 0;
for(int i = l; i <= r; i++) ans += (A[i] >= val);
return ans;
}
for(int i = st[bl]; i <= en[bl]; i++) A[i] += addv[bl], Blo[i] += addv[bl]; addv[bl] = 0;
for(int i = st[br]; i <= en[br]; i++) A[i] += addv[br], Blo[i] += addv[br]; addv[br] = 0;
for(int i = l; i <= en[bl]; i++) ans += (A[i] >= val);
for(int i = st[br]; i <= r; i++) ans += (A[i] >= val);
for(int i = bl + 1; i <= br - 1; i++) {
int x = lower_bound(Blo + st[i], Blo + en[i] + 1, val - addv[i]) - Blo;
if(Blo[x] >= val - addv[i]) x--;
if(en[i] > x) ans += en[i] - x;
}
return ans;
}
int main() {
n = read(); q = read();
int t = (int)(sqrt(n) + .5);
for(int i = 1; i <= n; i++) {
A[i] = Blo[i] = read();
int ni = (i - 1) / t + 1; cb = ni;
if(!st[ni]) st[ni] = i; en[ni] = i;
pos[i] = ni;
}
for(int i = 1; i <= cb; i++) sort(Blo + st[i], Blo + en[i] + 1);
while(q--) {
char tp = Getchar();
while(!isalpha(tp)) tp = Getchar();
int ql = read(), qr = read(), val = read();
if(tp == ‘M‘) update(ql, qr, val);
if(tp == ‘A‘) printf("%d\n", query(ql, qr, val));
}
return 0;
}
教主的这个魔法能不能在我身上用一下啊 QAQ
原文：http://www.cnblogs.com/xiao-ju-ruo-xjr/p/5744499.html