BZOJ 1568: [JSOI2008]Blue Mary开公司

正文索引 [隐藏]

Description
Sample Input
Sample Output
HINT
题解
代码

Description

Input
第一行：一个整数N ，表示方案和询问的总数。接下来N行，每行开头一个单词“Query”或“Project”。若单词为Query，则后接一个整数T，表示Blue Mary询问第T天的最大收益。若单词为Project，则后接两个实数S，P，表示该种设计方案第一天的收益S，以及以后每天比上一天多出的收益P。
Output
对于每一个Query，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，例如：该天最大收益为210或290时，均应该输出2）。

Sample Input

5
Query 2
Project 0 100
Query 2
Project 280 10
Query 2
Project 290 10
Query 2

Sample Output

1
2
3

HINT

约定：
1 <= N <= 100000
1 <= T <=50000
0 < P < 100，| S | <= 10^6
提示：本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。

题解

Orz考前手感差QAQ！写个线段树也写成了SB、、、
这道题目我们可以发现任意每次加入的Project都是在一段连续的区间里最优的，节点中只要记录序列开头s和公差d，然后更新就可以了。

代码

/*
  Author:WNJXYK
  WebSite:http://wnjxyk.cn
  Weibo:http://weibo.com/WNJXYK
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=50010;
int n=50000;
struct Btree{
    int left,right;
    int id;
    double s,d;
    Btree(){
        s=0;d=0;id=0;
    }
    inline double get(int k){
        return s+(double)k*d;
    }
};
inline bool bigger(Btree a,Btree b,int x){
    if (!b.id) return true;
    if (a.get(x)!=b.get(x)) return a.get(x)>b.get(x);
    return a.id>b.id;
}
Btree tree[Maxn*4+5];
Btree Query(int x,int l,int r,int pos){
    //printf("Index:%dn",x);
    if (l==r && l==pos) return tree[x];
    int mid=(l+r)/2;
    Btree tmp;
    if (pos<=mid) tmp=Query(x*2,l,mid,pos);
    if (pos>mid) tmp=Query(x*2+1,mid+1,r,pos);
    return bigger(tmp,tree[x],pos)?tmp:tree[x];
}
void insert(int x,int l,int r,Btree ins){
    //printf("Insert %dn",ins.s);
    if (!tree[x].id) tree[x]=ins;
    if (bigger(ins,tree[x],l)) swap(tree[x],ins);
    if (l==r || tree[x].d==ins.d) return;
    double tmp=(tree[x].s-ins.s)/(ins.d-tree[x].d);
    if (tmp<l || tmp>r) return;
    int mid=(l+r)/2;
    if (tmp<=mid) insert(x*2,l,mid,tree[x]),tree[x]=ins;
    if (tmp>mid) insert(x*2+1,mid+1,r,ins);
}
void insert(int x,int l,int r,int left,int right,Btree ins){
    //printf("%Ins:%lfn",ins.s);
    if (left<=l && r<=right){
        insert(x,l,r,ins);
    }else{
        int mid=(l+r)/2;
        if (left<=mid)insert(x*2,l,mid,left,right,ins);
        if (right>mid)insert(x*2+1,mid+1,r,left,right,ins);
    }
}
int main(){
    int m;
    scanf("%d",&m);
    char ch[15];
    while(~scanf("%s",&ch)){
        if (ch[0]=='Q'){
            int k;
            scanf("%d",&k);
            printf("%lldn",(long long)(Query(1,1,n,k).get(k)/100));
        }
        if (ch[0]=='P'){
            double s,d;
            scanf("%lf%lf",&s,&d);
            Btree tmp;
            tmp.s=s-d;tmp.d=d;tmp.id=1;
            insert(1,1,n,1,n,tmp);
        }
    }
    return 0;
}

Author:WNJXYK

WebSite:http://wnjxyk.cn

Weibo:http://weibo.com/WNJXYK

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int Maxn=50010;

int n=50000;

struct Btree{

int left,right;

int id;

double s,d;

Btree(){

s=0;d=0;id=0;

}

inline double get(int k){

return s+(double)k*d;

}

};

inline bool bigger(Btree a,Btree b,int x){

if (!b.id) return true;

if (a.get(x)!=b.get(x)) return a.get(x)>b.get(x);

return a.id>b.id;

}

Btree tree[Maxn*4+5];

Btree Query(int x,int l,int r,int pos){

//printf("Index:%dn",x);

if (l==r && l==pos) return tree[x];

int mid=(l+r)/2;

Btree tmp;

if (pos<=mid) tmp=Query(x*2,l,mid,pos);

if (pos>mid) tmp=Query(x*2+1,mid+1,r,pos);

return bigger(tmp,tree[x],pos)?tmp:tree[x];

}

void insert(int x,int l,int r,Btree ins){

//printf("Insert %dn",ins.s);

if (!tree[x].id) tree[x]=ins;

if (bigger(ins,tree[x],l)) swap(tree[x],ins);

if (l==r || tree[x].d==ins.d) return;

double tmp=(tree[x].s-ins.s)/(ins.d-tree[x].d);

if (tmp<l || tmp>r) return;

int mid=(l+r)/2;

if (tmp<=mid) insert(x*2,l,mid,tree[x]),tree[x]=ins;

if (tmp>mid) insert(x*2+1,mid+1,r,ins);

}

void insert(int x,int l,int r,int left,int right,Btree ins){

//printf("%Ins:%lfn",ins.s);

if (left<=l && r<=right){

insert(x,l,r,ins);

}else{

int mid=(l+r)/2;

if (left<=mid)insert(x*2,l,mid,left,right,ins);

if (right>mid)insert(x*2+1,mid+1,r,left,right,ins);

}

int main(){

int m;

scanf("%d",&m);

char ch[15];

while(~scanf("%s",&ch)){

if (ch[0]=='Q'){

int k;

scanf("%d",&k);

printf("%lldn",(long long)(Query(1,1,n,k).get(k)/100));

}

if (ch[0]=='P'){

double s,d;

scanf("%lf%lf",&s,&d);

Btree tmp;

tmp.s=s-d;tmp.d=d;tmp.id=1;

insert(1,1,n,1,n,tmp);

}

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑