题目链接: https://vjudge.net/contest/332656#problem/E
思路:
lmax 记录左边开始的最大连续区间, rmax 记录右边开始的最大连续区间 然后维护这两个值就可以了
主要是利用了线段树 (nod<<1) , ((nod<<1)+1) 所记录的区间是连续的特点
具体的解释还是看代码注释吧
- #include <math.h>
- #include <stdio.h>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <vector>
- #include <map>
- #include <stack>
- #include <random>
- #define LL long long
- const int maxn = 1e5 + 10;
- struct segment_tree {
- int l,r;
- int lmax,rmax;
- }tree[maxn<<2];
- void build(int l,int r,int nod) {
- tree[nod].l = l;
- tree[nod].r = r;
- tree[nod].lmax = tree[nod].rmax = r - l + 1;
- if (l == r) {
- return ;
- }
- int mid = (l + r)>> 1;
- build(l,mid,nod<<1);
- build(mid+1,r,(nod<<1)+1);
- }
- void pushup(int k) {
- tree[k].lmax = tree[k<<1].lmax;
- if (tree[k<<1].lmax + tree[k<<1].l - 1 == tree[k<<1].r) { // 右临界点 == 区间的右端点
- tree[k].lmax += tree[(k<<1)+1].lmax;
- }
- tree[k].rmax = tree[(k<<1)+1].rmax;
- if (tree[(k<<1)+1].r - tree[(k<<1)+1].rmax + 1 == tree[(k<<1)+1].l) { // 左临界点 == 区间的左端点
- tree[k].rmax += tree[k<<1].rmax;
- }
- }
- void modify(int v,int x,int k=1) {
- if (tree[k].l == tree[k].r ) {
- tree[k].lmax = tree[k].rmax = v;
- return ;
- }
- int mid = (tree[k].l + tree[k].r)>> 1;
- if (x <= mid) {
- modify(v,x,k<<1);
- } else {
- modify(v,x,(k<<1)+1);
- }
- pushup(k);
- }
- int query(int x,int k=1) {
- if (tree[k].l == tree[k].r) {
- return tree[k].lmax;
- }
- int mid = (tree[k].l + tree[k].r)>> 1;
- if (x <= mid) { // 查询左子树
- if (x>= tree[k<<1].r - tree[k<<1].rmax + 1) { // x>= 左临界点
- return tree[k<<1].rmax + tree[(k<<1)+1].lmax; // 左边区间的 rmax + 右边区间 lmax
- } else {
- return query(x,k<<1);
- }
- }
- else { // 查询右子树
- if (x <= tree[(k<<1)+1].lmax + tree[(k<<1)+1].l - 1) { // x <= 右临界点
- return tree[k<<1].rmax + tree[(k<<1)+1].lmax; // 左边区间的 rmax + 右边区间的 lmax
- } else {
- return query(x,(k<<1)+1);
- }
- }
- }
- int main() {
- int n,m,x;
- char s[2];
- while (~scanf("%d%d",&n,&m)) {
- std::stack<int> sta;
- build(1,n,1);
- while (m--) {
- scanf("%s",s);
- if (s[0] == 'D') {
- scanf("%d",&x);
- modify(0,x);
- sta.push(x);
- }
- else if (s[0] == 'R') {
- x = sta.top();
- sta.pop();
- if (x> 0)
- modify(1,x);
- }
- else {
- scanf("%d",&x);
- printf("%d\n",query(x));
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3232639.html