傳送門：戳我

在cf上做的鏡像賽，結(jié)果不是很妙啊。。

這題是用時最長但并沒有在比賽內(nèi)寫出來（事實上在賽后還話了大概五小時調(diào)試才找出錯誤）

首先不難發(fā)現(xiàn)我們需要一棵線段樹，（其實一開始我考慮的是主席樹）。。。

然后發(fā)現(xiàn)很難維護(hù)區(qū)間信息。于是，考慮權(quán)值線段樹（然而實際上是sugar大佬提醒我要用權(quán)值線段樹）。

考慮掃描線。把每天銷售方案的進(jìn)出信息用一個鄰接表存起來，我這里用的vector實現(xiàn)。然后每天該進(jìn)的進(jìn)，該出的出（根據(jù)差分思想，物品銷售到r天，在r+1天出，我在這里卡了10分鐘。。），處理完，然后在權(quán)值線段樹上找到K所在的結(jié)點。

這里解釋一下，就是找到當(dāng)前可用的物品的第K個。以前沒接觸過這種類型的查詢，，然后寫了一個二分答案，，最后結(jié)果是NlogNlogN，沒卡過1e6（哭）。比賽結(jié)束后在sugar大佬的指導(dǎo)下，把查找改成了logN的查找。就是找權(quán)值線段樹上找第K個元素。這里對于查詢一個權(quán)值線段樹一個非葉子結(jié)點第a個元素，判斷左子樹的總數(shù)是否大于a，大于則遞歸到左子樹，否則遞歸到右子樹（記得a要減去左子樹的元素個數(shù)，因為你遞歸下來查找的是右子樹第b個元素，而原來的a是左子樹的元素個數(shù)+b）。

然后我們還需要一棵線段樹，以單價為區(qū)間，維護(hù)信息為取完這些需要多少錢。舉個例子解釋，比如我查詢l到r，返回結(jié)果是買完大于等于l元，小于等于r元的所有物品的總價錢。然后不難發(fā)現(xiàn)，這棵線段樹的結(jié)構(gòu)和我們之前的權(quán)值線段樹是一樣的且更新是同步的。所以可以并到一起寫。

這里搞定后然后處理細(xì)節(jié)問題。

如果一個時刻，掃描線（權(quán)值線段樹）上所有元素之和小于等于K，那么我顯然直接取完，進(jìn)入下一天。

如果大于K，那么二分找到需要取到f元才能取到大于等于K個物品。我們會發(fā)現(xiàn)，取完1到f可能會取多，那么減去取多的部分產(chǎn)生的價錢。也就是在權(quán)值線段樹上查找取到f有幾個物品，然后減去K，差值乘上f就是要減去的部分的價錢。

然后把每天的值加起來，就是最后的答案了。

對本蒟蒻來說代碼實現(xiàn)難度略高，調(diào)試略難。

以下為代碼：

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #define maxn 1000005 using namespace std; vector<int>in[maxn]; vector<int>out[maxn]; namespace solution{long long ANS=0;inline void read(int &x){x=0;int f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}x*=f;}int N,K,M,n;struct node{long long l,r;long long sum;long long add;}tree[maxn<<2];inline void push_up(int rt){tree[rt].add=tree[rt<<1].add+tree[rt<<1|1].add;tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;}void build(int rt,int l,int r){tree[rt].l=l;tree[rt].r=r;if(l==r)return ;long long mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);}void update(int rt,int p,long long x){//cout<<"update note: "<<tree[rt].l<<" "<<tree[rt].r<<" "<<p<<" "<<x<<endl; if(tree[rt].l==tree[rt].r){tree[rt].sum+=x;tree[rt].add+=x*p;return ;}int mid=tree[rt].l+tree[rt].r>>1;if(p<=mid)update(rt<<1,p,x);elseupdate(rt<<1|1,p,x);push_up(rt);}long long query(int rt,int l,int r){//cout<<"query note: "<<tree[rt].l<<" "<<tree[rt].r<<" "<<l<<" "<<r<<endl;if(l<=tree[rt].l&&tree[rt].r<=r)return tree[rt].sum;int mid=tree[rt].l+tree[rt].r>>1;long long ans=0;if(l<=mid)ans+=query(rt<<1,l,r);if(r>mid)ans+=query(rt<<1|1,l,r);return ans;}long long query_add(int rt,int l,int r){// cout<<"query note: "<<tree[rt].l<<" "<<tree[rt].r<<" "<<tree[rt].add<<endl;if(l<=tree[rt].l&&tree[rt].r<=r)return tree[rt].add;int mid=tree[rt].l+tree[rt].r>>1;long long ans=0;if(l<=mid)ans+=query_add(rt<<1,l,r);if(r>mid)ans+=query_add(rt<<1|1,l,r);return ans;}struct plan{int l,r,p,c;friend bool operator < (plan a,plan b){return a.l<b.l;}}plan[maxn];void getin(){read(N);read(K);read(M);for(int i=1;i<=M;i++){read(plan[i].l);read(plan[i].r);read(plan[i].c);read(plan[i].p);n=max(n,plan[i].p);in[plan[i].l].push_back(i);out[plan[i].r+1].push_back(i);}}long long find(int rt,int k){// cout<<"find note: "<<tree[rt].l<<" "<<tree[rt].r<<" "<<tree[rt<<1].sum<<endl; if(tree[rt].l==tree[rt].r)return tree[rt].l;int mid=tree[rt].l+tree[rt].r>>1;if(tree[rt<<1].sum>=k)return find(rt<<1,k);elsereturn find(rt<<1|1,k-tree[rt<<1].sum);/*int l=1,r=n,mid,ans=n;while(l<=r){mid=l+r>>1;//cout<<"find note: "<<l<<" "<<r<<" "<<mid<<" "<<query(1,1,mid)<<endl; if(query(1,1,mid)>=K)r=mid-1,ans=mid;elsel=mid+1;}return ans;*/}void work(){for(int i=1;i<=N;i++){for(vector<int>::iterator it=in[i].begin();it!=in[i].end();it++) {int top=*it;//cout<<"in note: "<<top<<" "<<plan[top].p<<" "<<plan[top].c<<" ";update(1,plan[top].p,plan[top].c);//cout<<query(1,1,plan[top].p)<<endl; }for(vector<int>::iterator it=out[i].begin();it!=out[i].end();it++){int top=*it;//cout<<"out note:"<<top<<endl;update(1,plan[top].p,plan[top].c*-1);}long long tot=query(1,1,n);int f=0;if(tot<=K)ANS+=query_add(1,1,n);else{f=find(1,K);long long d=query_add(1,1,f)-(query(1,1,f)-K)*f;// cout<<"NOTE: "<<query_add(1,1,f)<<" "<<query(1,1,f)<<endl;ANS+=d;}//cout<<"day:"<<i<<" "<<f<<" "<<ANS<<endl; }}void put_out(){printf("%lld",ANS);}void solve(){getin();build(1,1,n);work();put_out();} } int main() {solution::solve(); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sherrlock/p/9826828.html

總結(jié)

以上是生活随笔為你收集整理的[CodeForces1070C]Cloud Computing(2018-2019 ICPC, NEERC, Southern Subregional Contest )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。