BZOJ 1858 [SCOI2010] 序列操作

本来想用线段树做,但是考虑到用线段树的话pushup,pushdown函数有点复杂...
看到题目有覆盖操作立刻想到了珂朵莉树,于是现学了一波然后改了一下模板A了这道题。
(珂学是个好东西)
(刷这道题全程循环夢違科(珂)学世紀2333333)

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>

#define __node_it set<node>::iterator

using namespace std;

//define
const int maxn = 1e5 + 5;
struct node{
    mutable int l, r, v;
    node(int L,int R = -1, int V = 0):l(L), r(R), v(V){}
    bool operator < (const node& rhs) const{
        return l < rhs.l;
    }
};
int n, m;
set<node> s;

__node_it split(int rt){
    __node_it it = s.lower_bound(node(rt));
    if(it != s.end() && it->l == rt)return it;
    --it;int ll = it->l, rr = it-> r, vv = it->v;
    s.erase(it);
    s.insert(node(ll, rt - 1, vv));
    return s.insert(node(rt, rr, vv)).first;
}

void assign(int l, int r, int v){
    __node_it itr = split(r + 1), itl = split(l);
    s.erase(itl, itr);
    s.insert(node(l, r, v));
}

int sum(int l, int r){
    int ans = 0;
    __node_it itr = split(r + 1), itl = split(l);
    for(; itl != itr; ++itl){
        ans += itl->v ? itl->r - itl->l + 1:0;
    }
    return ans;
}

void reverse(int l, int r){
    __node_it itr = split(r + 1), itl = split(l);
    for(; itl != itr; ++itl){
        itl->v ^= 1;
    }
}

int cnt(int l, int r){
    int ans = -0x7f7f7f7f, cnt = 0;
    __node_it itr = split(r + 1), itl = split(l);
    for(; itl != itr; ++itl){
        if(itl->v == 1){
            cnt += itl->r - itl->l + 1;
            //cout << "NM$L" << cnt << endl;
        }
        else{
            cnt = 0;
        }
        ans = max(ans, cnt);
    }
    return ans;
}

//main
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;int tmp;
    for(register int i = 0; i < n; ++i){
        cin >> tmp;
        s.insert(node(i, i, tmp));
    }
    int x, y, z, a;
    while(m--){
        cin >> x;
        switch(x){
            case 0:
                cin >> y >> z;
                assign(y, z, 0);
                break;
            case 1:
                cin >> y >> z;
                assign(y, z, 1);
                break;
            case 2:
                cin >> y >> z;
                reverse(y, z);
                break;
            case 3:
                cin >> y >> z;
                cout << sum(y, z) << endl;
                break;
            case 4:
                cin >> y >> z;
                cout << cnt(y, z) << endl;
                break;
        }
    }
    return 0;
}
Tags:数据结构暴力
上一篇
下一篇

该页面评论已关闭