[SCOI2010]序列操作 题解报告

· · 题解

本来是一道线段树的好题，结果被ODT(珂朵莉树)暴力+玄学跑过......

不过这也是珂朵莉树新学者的很好的板子题诶

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define IT set<node>::iterator
struct node{
    int l,r;
    mutable int val;
    bool operator < (const node &x) const{
        return l<x.l;
    }
};
set<node>tr;
IT split(int pos)
{
    IT iter=tr.lower_bound((node){pos});
    if(iter!=tr.end()&&iter->l==pos)
        return iter;
    iter--;
    int nwl=iter->l,nwr=iter->r,nwval=iter->val;
    tr.erase(iter);
    tr.insert((node){nwl,pos-1,nwval});
    return tr.insert((node){pos,nwr,nwval}).first;
}
void assign(int l,int r,int val)
{
    IT iter_r=split(r+1),iter_l=split(l);
    tr.erase(iter_l,iter_r);
    tr.insert((node){l,r,val});
    return;
}
void fiu(int l,int r)
{
    IT iter_r=split(r+1),iter_l=split(l);
    for(;iter_l!=iter_r;++iter_l)
        iter_l->val=iter_l->val==1?0:1;
    return;
}
int query(int l,int r)
{
    IT iter_r=split(r+1),iter_l=split(l);
    int ans=0;
    for(;iter_l!=iter_r;++iter_l)
        ans+=(iter_l->val)*(iter_l->r-iter_l->l+1);
    return ans;
}
int QAQ(int l,int r)
{
    IT iter_r=split(r+1),iter_l=split(l);
    int mx=0,sum=0;
    for(;iter_l!=iter_r;++iter_l)
        if(iter_l->val==1)
        {
            int pop=iter_l->r-iter_l->l+1;
            sum+=pop;
        }
        else mx=max(mx,sum),sum=0;
    return max(mx,sum);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        tr.insert((node){i,i,x});
    }
    tr.insert((node){n,n,0});
    while(m--)
    {
        int kkk,a,b;
        scanf("%d%d%d",&kkk,&a,&b);
        if(kkk==0) assign(a,b,0);
        if(kkk==1) assign(a,b,1);
        if(kkk==2) fiu(a,b);
        if(kkk==3) printf("%d\n",query(a,b));
        if(kkk==4) printf("%d\n",QAQ(a,b));
    }
    return 0;
}

不过如果没有区间赋值这一层操作的话，ODT退化下来还是O(n^2)的吧...

不得不说ODT处理随机数据的复杂度还真是蛮玄学的