http://acm.uestc.edu.cn/#/problem/show/1157
数列(seq)
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 128000/128000KB (Java/Others)
给出一个长度为n的数列A。现有如下两种操作：
修改操作：把数列中第i个数改为x
询问操作：给定一个位置i，问数列中有多少个位置j ( j>i )，满足位置i与位置j间所有的数都不超过Ai与Aj的较大值。
现共有m个操作，请对每个询问操作做出回答。
Input
第一行两个正整数n、m。
随后n行，每行一个正整数Ai。
随后m行，若是修改操作，则以一个大写C开头，随后两个正整数i和x；若是查询操作，则以一个大写Q开头，随后一个正整数i。
Output
每行一个整数，依次对每个询问操作给出回答。
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 3 |
2 |
Hint
对于40%的数据，n、m<=5000
对于100%的数据，n、m<=50000，|Ai|、x<=100000
思路：
这种xjb更新的，一般就是分块了
首先分析题目以后发现，对于区间[i,j]，其中(i,j)之间所有的数值都是小于max(a[i], a[j])的。然后我们又可以发现，每一个数值a[i]，其都会维护一个区间(即[x, i])，且[x,i]中的所有数值都<=a[i]。
修改、更新操作：
接下来我们分块，对于每个块，我们维护块中的最大值（用maxval纪律）和 块中的每个position能延伸到块的左边界的数（将这个数值放到vector里面去），之所以要延伸到最左端，是因为只有能够延伸到最左端的才有资格让[x,j]区间内所有的数值都小于max(a[x],a[j])。 所以这一步的复杂度为sqrt(n)
询问操作：
左区间，暴力：
如果Max == a[x]，那么把所有的a[i] <=a[x]的都ans++，
不然的话,只有a[i]>= Max，才能ans++
中间块的话，
①
如果maxval=a[x]，那么就判断是否>=maxval[i]
if (true) ans+=目前块的大小
else 暴力目前的块
如果Max == a[x]，同左区间的分类讨论
②如果maxval>a[x]，那么我们就二分即可，看看有多少能连接到左边界
右区间，暴力：
同左区间。
所以这里的复杂度为sqrt(n) * log(n)
总的复杂度为O(m * sqrt(n) * log(n))
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
/*
对于某个数，我们要知道他到块的左端的所有数值都是比他小的才行
我们可以知道，每个position，向左边都可以维护一个特定的区间，
然后我们对块中，看看有哪些能够维护到左边界的，并且放到vector里面排序,而且
放入vector里面的顺序一定是有序的，
因此，上面是修改操作，复杂度为sqrt(n) 对于询问操作，我们每次就只需要判断即可,对于边缘的块，我们暴力
对于完整的块，我们二分即可。所以总的复杂度为sqrt(n) * log(n)。
*/
const int inf = 0x3f3f3f3f;
const int maxn = + ;
int n, m;
int a[maxn];
int num, block, belong[maxn], l[maxn], r[maxn];
int maxval[maxn];//目前块的最大值
vector<int> ve[maxn];//目前该块能到最左边的有几个 void build(){
block = sqrt(n); num = n / block;
if (n % block) num++;
for (int i = ; i <= num; i++){
l[i] = (i - ) * block + , r[i] = i * block;
}
r[num] = n;
for (int i = ; i <= n; i++)
belong[i] = (i - ) / block + ;
} void update(int be){
int Max = -inf;
ve[be].clear();
for (int i = l[be]; i <= r[be]; i++){
if (a[i] >= Max) {
ve[be].push_back(a[i]); Max = a[i];
}
}
maxval[be] = Max;
} int query(int x, int y){
int ans = , Max = a[x];
if (belong[x] == belong[y]){
for (int i = x + ; i <= y; i++){
if (a[i] >= Max) {Max = a[i]; ans++;}
else if(a[x] == Max) ans++;
}
return ans;
}
for (int i = x + ; i <= r[belong[x]]; i++){
if (a[i] >= Max){Max = a[i]; ans++;}
else if(a[x] == Max) ans++;
}
//printf("ans = %d\n", ans);
for (int i = belong[x] + ; i < belong[y]; i++){
if (a[x] == Max){
if (Max >= maxval[i]) ans += r[i] - l[i] + ;
else {
for (int j = l[i]; j <= r[i]; j++){
if (a[j] >= Max) {Max = a[j]; ans++;}
else if(a[x] == Max) ans++;
}
}
}
else {
int pos = lower_bound(ALL(ve[i]), Max) - ve[i].begin() + ;
ans += ve[i].size() + - pos;
Max = max(Max, maxval[i]);
}
}
//printf("ans = %d\n", ans);
for (int i = l[belong[y]]; i <= y; i++){
if (a[i] >= Max){Max = a[i]; ans++;}
else if(a[x] == Max) ans++;
}
//printf("ans = %d\n", ans);
return ans;
} int main(){
cin >> n >> m;
for (int i = ; i <= n; i++) scanf("%d", a + i);
build();
for (int i = ; i <= num; i++){
update(i);
}
while (m--){
char ch[]; int i, x;
scanf("%s%d", ch, &i);
if (ch[] == 'C'){
scanf("%d", &x); a[i] = x;
update(belong[i]);
}
else {
printf("%d\n", query(i, n));
}
}
return ;
}
/*
10 1
9284 15645 17127 23946 2177 12658 9740 29482 24450 25110
Q 4
ans = 4
*/