公司做网站一般要多少钱,整站优化加盟,电商型网站建设,网站工作室模板Problem D 发布时间: 2017年6月28日 10:51 最后更新: 2017年6月28日 16:38 时间限制: 1000ms 内存限制: 32M 描述 给定一个长度为n的序列a1, a2, ..., an当k满足2≤k≤n−1, akak−1且akak1时, 将元素k称为极大值点, 给出q个操作, 操作分为两种 对于形如1xy的操作… Problem D 发布时间: 2017年6月28日 10:51 最后更新: 2017年6月28日 16:38 时间限制: 1000ms 内存限制: 32M 描述 给定一个长度为n的序列a1, a2, ..., an 当k满足2≤k≤n−1, akak−1且akak1时, 将元素k称为极大值点, 给出q个操作, 操作分为两种 对于形如1 x y的操作, 将ax修改为y, 满足1≤x≤n, 1≤y≤109 对于形如2 x y的操作, 输出区间[x,y]内有多少个极大值点, 满足1≤x≤y≤n 9×104≤n≤105, 9×104≤q≤105, 1≤ai≤109 输入 第一行两个整数n, q, 意义如上所述。 第二行n个整数, 表示序列a。 接下来q行, 每行第一个数为opt, 之后紧跟两个数, 意义如上所述。 输出 对于每个操作2, 输出答案, 一行一个。 样例输入1 复制 8 3
3 1 4 1 5 9 2 6
2 1 8
1 3 1
2 1 8 样例输出1 2
1 我们可以直接创建一个树状数组如果某个元素x是极大值那么我们就往蜀树状数组相应的位置写上1这样的话想要统计区间最大值的个数只需要
统计树状数组的区间和就可以了。
而在维护的时候修改a[x] 为y要小心的考虑
这里举一个例子要将a[x]改为y的情况
1如果修改前a[x]是极大值修改后a[x]非极大值那么add(x,-1)
2如果修改前a[x]非极大值修改后a[x]为极大值那add(x,-1)
3.。。注意a[x]改成y不光影响x出的值x-1x1处都有可能被影响
。。。要注意
代码 #include iostream
#include cstdio
using namespace std;
const int MAX 1e57;
int n,q;
int a[MAX];
int b[MAX];
inline int lowbit(int x){return x (-x);
}
int getsum(int pos){int res 0;while(pos){res b[pos];pos - lowbit(pos);}return res;
}
void add(int pos,int val){while(pos n){b[pos] val;pos lowbit(pos);}
}
inline bool check(int pos){return a[pos] a[pos1] a[pos] a[pos-1];
}int main(){scanf(%d%d,n,q);for(int i 1;i n;i){scanf(%d,a[i]);}for(int i 2;i n;i){if(check(i)){add(i,1);}}while(q--){int opt;scanf(%d,opt);if(opt 1){int x,y;scanf(%d%d,x,y);if(x 1){if(!check(2) (a[2] y a[2] a[3])){add(2,1);}if(check(2) !(a[2] y a[2] a[3])){add(2,-1);}}else if(x n){if(!check(n-1) (a[n-1] a[n-2] a[n-1] y)){add(n-1,1);}if(check(n-1) !(a[n-1] a[n-2] a[n-1] y)){add(n-1,-1);}}else{if(!check(x) (y a[x-1] y a[x1]) ){add(x,1);}if(check(x) !(y a[x-1] y a[x1]) ){add(x,-1);}if(x 3 !check(x-1) (a[x-1] a[x-2] a[x-1] y)){add(x-1,1);}if(x 3 check(x-1) !(a[x-1] a[x-2] a[x-1] y)){add(x-1,-1);}if(x n-2 !check(x1) (a[x1] a[x2] a[x1] y)){add(x1,1);}if(x n-2 check(x1) !(a[x1] a[x2] a[x1] y)){add(x1,-1);}}a[x] y;}else{int x,y ;scanf(%d%d,x,y);printf(%d\n,getsum(y) - getsum(x-1));}}return 0;
}
