没错还是这一场比赛,我好像和它杠上了

迟到一天的题解

题意:

你正在修城墙

一开始,所有城墙等级为1级

你可以指定两个长度为r的区间,让这两个区间的城墙各升1级

之后,你需要支付以下价格:

对于第i块城墙,1级城墙的价格为ai,2级为bi,3级为ci

保证1<=ai<bi<ci<=1e6,保证n<=30000,1<=r<n

那么你一共有(n-r)*(n-r+1)/2

求第k小的价格

思路:

我们知道,一共有(n-r)*(n-r+1)/2种方案

如果我们直接枚举出来肯定是不行的

所以我想到了一个办法,二分

二分答案,然后判定是否可行

判定的时候,如果两个区间不相交就是两个bi的事情

这个东西直接用一个数据结构维护一下

数据结构要求:支持插入,支持求有多少个数比某个询问的数字小....

第二个操作...有点坑.....不能STL....可以离线线段树..当然我写了个treap

还有一种情况是重叠的

我们考虑把重叠的东西丢进一个treap里,每次删除一个,插入一个

并且执行一次整体加法

因为我们将bi升级成了ci,所以要支付的要加(ci-bi)-(bi-ai)

二分的时候统计是否有k个比它小的(或者等的)

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[30005],b[30005],c[30005];
int n,r;
long long ans=0;
struct node
{
    long long val;
    int size;
    int weight;
    node * ch[2]; 
};
int top=0;
node * null;
node * new_node(long long x=0)
{
    static node a[80005];
    a[top].val=x;
    a[top].size=1;
    a[top].weight=rand()+rand()<<15;
    a[top].ch[0]=null;
    a[top].ch[1]=null;
    return &a[top++];
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]=x;
    y->size=x->size;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    x=y;
}
void insert_node(node * &x,node * y)
{
    if (x==null)
    {
        x=y;
        return;
    }
    x->size++;
    int c;
    if (y->val>x->val)
    {
        c=1;
    }
    else
    {
        c=0;
    }
    insert_node(x->ch[c],y);
    if (x->ch[c]->weight>x->weight) rotate(x,c);
}
void delete_node(node * &x,const long long &val)
{
    if (x==null)
    {
        return;
    }
    x->size--;
    if (x->val==val)
    {
        int c;
        if (x->ch[0]->weight>x->ch[1]->weight)
        {
            c=0;
        }
        else
        {
            c=1;
        }
        if (x->ch[c]==null)
        {
            x=null;
            return;
        }
        rotate(x,c);
        delete_node(x->ch[!c],val);
    }
    else
    {
        if (val<x->val)
        {
            delete_node(x->ch[0],val);
        }
        else
        {
            delete_node(x->ch[1],val);
        }
    }
}
int find_val(node * now,long long val)
{
    if (now==null) return 0;
    if (val>=now->val)
    {
        return now->ch[0]->size+1+find_val(now->ch[1],val);
    }
    else
    {
        return find_val(now->ch[0],val);
    }
}
bool check(long long mid,int k)
{
    mid-=ans;
    static long long sums[30005];
    srand(0);
    top=0;
    null=new_node();
    null->ch[0]=null;
    null->ch[1]=null;
    null->val=-1;
    null->weight=-1;
    null->size=0;
    node * root=null;
    long long sum=0;
    long long now=0;
    int i;
    for (i=0;i<r;i++)
    {
        sum+=b[i];
        now+=c[i];
    }
    for (;i<r+r;i++)
    {
        if (i>=n) break;
        now-=c[i-r];
        now+=b[i];
        sums[i-r]=now;
        insert_node(root,new_node(now));
    }
    node * root2=null;
    for (;i<n;i++)
    {
        now-=b[i-r];
        now+=b[i];
        sums[i-r]=now;
        insert_node(root2,new_node(now));
    }
    now=0;
    int cnt=0;
    cnt+=find_val(root,mid-sum);
    cnt+=find_val(root2,mid-sum);
    if (cnt>=k) return true;
    for (i=r;i<n;i++)
    {
        delete_node(root,sums[i-r]);
        sum-=b[i-r];
        sum+=b[i];
        now+=c[i]-b[i];
        if (i+r<n)
        {
            delete_node(root2,sums[i]);
            sums[i]-=now;
            insert_node(root,new_node(sums[i]));
        }
        cnt+=find_val(root,mid-sum-now);
        cnt+=find_val(root2,mid-sum);
        if (cnt>=k) return true;
    }
    return false;
}
int main()
{
    //srand(time(0));
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d%d",&n,&r);
    int i;
    int k;
    scanf("%d",&k);
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
    }
    for (i=0;i<n;i++)
    {
        scanf("%d",&c[i]);
    }
    long long max_val=0;
    for (i=0;i<n;i++)
    {
        max_val+=c[i];
        ans+=a[i];
        c[i]-=b[i];
        b[i]-=a[i];
    }
    long long l=ans,r=max_val;
    for (;l<=r;)
    {
        long long mid=(l+r)/2;
        if (check(mid,k))
        {
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<l<<endl;
    return 0;
}