题解 P2572 【[SCOI2010]序列操作】

2018-10-03 19:14:10


三个月之前我第一次尝试这道题的时候,我写了将近4KB的线段树,WA得只有10分。

今天突然想起这道题,十几分钟就用珂朵莉树水过去了。当然由于这题数据不是随机的,珂朵莉树的复杂度是错的。五种操作中有两种是区间赋值,一种是反转,另外两种是查询。都可以用珂朵莉树split一波然后暴力搞定。

开O2之后475ms,速度和大多数线段树差不多吧。

#include<cstdio>
#include<cctype>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>
#define IT set<node>::iterator

int Read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))
    {
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

using std::set;
using std::vector;
using std::pair;

typedef long long LL;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int imax_n = 1e5 + 7;

struct node
{
    int l,r;
    mutable bool v;
    node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const
    {
        return l < o.l;
    }
};

set<node> s;

//split(pos)操作是指将原来含有pos位置的节点分成两部分:[l,pos−1]和[pos,r]
IT split(int pos)
{
    IT it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    bool V = it->v;
    s.erase(it);
    s.insert(node(L, pos-1, V));
    return s.insert(node(pos, R, V)).first;
    //这里利用了pair<iterator,bool> insert (const value_type& val)的返回值
}

//ass♂ign操作迅速减小set的规模
void assign_val(int l, int r, bool val)
{
    IT itr = split(r+1), itl = split(l);
    s.erase(itl, itr);
    //void erase (iterator first, iterator last)可删除[first,last)区间
    s.insert(node(l, r, val));
}

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

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

int conti(int l,int r)
{
    int res=0,temp=0;
    IT itr = split(r+1),itl = split(l);
    for(; itl != itr; ++itl)
    {
        if(itl->v == false)
        {
            res = std::max(res, temp);
            temp=0;
        }
        else
        {
            temp += itl->r - itl->l + 1;
        }
    }
    return std::max(res, temp);
}

LL a[imax_n];

int main()
{
    int n=Read(), m=Read();
    for (int i=0; i<n; ++i)
    {
        s.insert(node(i,i,Read()));
    }
    s.insert(node(n, n, 0));
    int op, a, b;
    for (int i =1; i <= m; ++i)
    {
        op=Read(), a=Read(), b=Read();
        if(op == 0)
        {
            assign_val(a, b, 0);
        }
        else if(op == 1)
        {
            assign_val(a, b, 1);
        }
        else if(op == 2)
        {
            rev(a, b);
        }
        else if(op == 3)
        {
            printf("%d\n",sum(a, b));
        }
        else
        {
            printf("%d\n",conti(a,b));
        }
    }
    return 0;
}