这道题的意思是给你一个水塔，可以从中间任意一层倒水，告诉你每一层的容量，这一曾层满后水会流入下一层，总共有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);
else
res=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);
else
most=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;
else
lb=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);
}
else
cout<<has[pos]<<endl;
}
return 0;
}