bzoj 4552: [Tjoi2016&Heoi2016]排序

标签：cin   friend   多少   main   end   space   fine   close   har   

ODT&二分

看到没有人写关于ODT的题解，所以我决定来一发ODT题解。

首先这道题的的整体思路就是二分，关于二分的正确性可以感性的理解一下：我们每一次二分一个答案，然后将\(的值变为1，\(\geq mid\)的变为0，每一次只用对0/1序列进行操作，倘若最后我们询问的位置上为0，说明这个位置上的值\(,否则就\(\geq mid\)，所以它就具有可二分性。

让我们看看对0/1序列的操作，每次排序就相当于整体的0/1序列排序，也就是区间推平操作，所以我们就珂以用幸福的ODT来做这道题啦.我们每一次只用询问一下这个区间里一共有多少个1，然后将\(l\)到\(l+len-1\)推平就好辣。当然这需要开O2(否则就死掉了)，实测开了O2后跑的快的飞起。

最后献上我丑陋的代码

#include
#include
#include
#include
#define IT set::iterator
using namespace std;
int n,m,opt,k,ll,rr,ans;
int a[100010];
int l[100010],r[100010];
int pan[100010];

int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&chs;



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;
    int V=it->val;
    s.erase(it);
    s.insert(node{L,pos-1,V});
    return s.insert(node{pos,R,V}).first;
}

int sum(int l,int r)
{
    IT it2=split(r+1),it1=split(l);
    int res=0;
    for(;it1!=it2;++it1)
    if(it1->val)res+=(it1->r-it1->l+1);
    return res;
}


void tuiping(int l,int r,int v)
{
    IT it2=split(r+1),it1=split(l);
    s.erase(it1,it2);
    s.insert(node{l,r,v});
}

int check(int x)
{
    s.clear();
    int val=(a[1]>=x),len=1;
    for(int i=2;i=x)!=val)
        {
            s.insert(node{i-len,i-1,val});
            val=(a[i]>=x);len=1;
        }
        else len++;
    }
    s.insert(node{n-len+1,n,val});
    s.insert(node{n+1,n+1,1});
    for(int i=1;i>k;
    int ans=0;
    ll=1;rr=n;//cout>1;
        if(check(mid))
        {
            ll=mid+1;
            ans=mid;
        }
        else rr=mid-1;
    }
    coutn>>m;
    for(int i=1;i

bzoj 4552: [Tjoi2016&Heoi2016]排序

标签：cin   friend   多少   main   end   space   fine   close   har   

原文地址：https://www.cnblogs.com/wljss/p/11559916.html