CodeForces Round 218 D. Vessels（学姐我没用线段树系列）

本文主要是介绍CodeForces Round 218 D. Vessels（学姐我没用线段树系列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题的意思是给你一个水塔，可以从中间任意一层倒水，告诉你每一层的容量，这一曾层满后水会流入下一层，总共有N层，再满了就直接流到地上。然后给出N个操作

操作1：往第n层中加x的水

操作2：询问每一层装有多少水

用BIT保存所剩空间的前缀和，每次加水的时候二分最终水会流到哪一层，然后加水的时候依次更新BIT，虽然式单点更新但是每一次更新都会直接把该层的空间沾满，下一次不会再更新，所以总共是O（n）次更新，总复杂度O(nlogn)。

为啥我不用线段树呢？为啥我不用线段树呢....因为这是个前缀和啊= =

另外今天试了试 

#define lld I64d  竟然能用

以后再也不怕CF只能交I64d了...

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long 
#define lld I64d
ll bit[300000];
ll n;
ll sum(ll i)
{ll s=0;while(i>0){s+=bit[i];i-=(i)&(-i);}return s;
}void add(ll i,ll x)
{while(i<=n){bit[i]+=x;i+=i&(-i);}
}ll num[300000];
ll init[300000];
bool C(ll x,ll l,ll r)
{ll res=0;if(l==0)res=sum(r);elseres=sum(r)-sum(l);if(res>=x)return true;return false;
}	int main()
{scanf("%lld",&n);for(ll i=1;i<=n;i++){int t;scanf("%lld",&num[i]);add(i,num[i]);init[i]=num[i];}ll m;scanf("%lld",&m);for(ll i=0;i<m;i++){int t;scanf("%d",&t);if(t==1){ll p,x;scanf("%lld%lld",&p,&x);ll most=0;if(p==1)most=sum(n);elsemost=sum(n)-sum(p-1);if(x>most)x=most;ll lb=p-1;ll ub=n+1;while(ub-lb>1){ll m=(lb+ub)>>1;if(C(x,p-1,m))ub=m;elselb=m;}for(ll i=p;i<=ub;i++){if(i!=ub){if(!num[i])continue;add(i,-num[i]);x-=num[i];num[i]=0;}else{add(i,-x);num[i]-=x;x=0;}}}if(t==2){ll ans;ll t;scanf("%lld",&t);printf("%lld\n",init[t]-num[t]);}	}return 0;
}

翻别人代码看..发现一个简单的要死的代码....

把有空的层放在set里面，直接向下更新然后erase。。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set># define pii pair<int,int>
# define ll long long
# define vi vector<int>
# define pb push_back
# define pp pop_back
# define mp make_pair
using namespace std;
const int maxn = 200005;int v[maxn],n;
int has[maxn],m;
set <int> S;void add(int k, int x)
{set <int>::iterator it = S.lower_bound(k);while (it != S.end() && x){int w=min(x , v[*it]-has[*it]);x-=w;has[*it]+=w;if (v[*it] == has[*it])S.erase(it++);}
}int main(){cin>>n;for(int i=1 ; i<=n ; i++){cin>>v[i];S.insert(i);}cin>>m;for(int i=1 ; i<=m ; i++){int q,pos,lit;cin>>q>>pos;if(q==1){cin>>lit;add(pos,lit);}elsecout<<has[pos]<<endl;}return 0;
}

这篇关于CodeForces Round 218 D. Vessels（学姐我没用线段树系列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---