absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] 101630K
[破碎的状态] 101630J

[破碎的状态] 101630G

absi2011 posted @ Mar 01, 2018 03:01:56 PM in 刷题记录 with tags CF Gym 小高考 Treap 二分 , 593 阅读

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

迟到一天的题解

题意:

你正在修城墙

一开始,所有城墙等级为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;
}
how to Add Signature 说:
Aug 09, 2022 01:28:24 AM

Gmail is a user-friendly interface that brings a lot of features to the users like Gmail Signature, Google Hangouts, and more. In case, you have to send multiple emails daily then you may allow to add Gmail Signature. how to Add Signature to Gmail This saves your time and also lets the body of mails have the signature of you as an individual or if as an entity.

HBSE Question Paper 说:
Sep 03, 2022 06:28:51 PM

Haryana Board Model Paper 2023 Class 7 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. HBSE Question Paper Class 7 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter