## 【HDU 5575】Discover Water Tank

### 解题报告

1. 区间水位低于$x$，那么我们分治$solve(l,x-1)+solve(x+1,r)$即可
2. 区间水位高于$x$，那么我们搞一个前缀和就好

## 【BZOJ 2809】[Apio2012] dispatching

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;

LL vout;
int led[N],n,m,arr[N],rt;
vector<int> G[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Skew_Heap{
#define SHP Skew_Heap
int ch[N][2],sz[N],val[N],root[N],cnt;
LL sum[N];

inline void maintain(int w) {
sz[w] = sz[ch[w][0]] + sz[ch[w][1]] + 1;
sum[w] = sum[ch[w][0]] + sum[ch[w][1]] + val[w];
}

int Merge(int a, int b){
if (!a || !b) return a+b;
else {
if (val[b] > val[a]) swap(a,b);
ch[a][1] = Merge(ch[a][1],b);
swap(ch[a][0],ch[a][1]); maintain(a);
return a;
}
}

inline void pop(int w){
root[w] = Merge(ch[root[w]][0],ch[root[w]][1]);
}

inline void insert(int w, int v){
val[++cnt] = sum[cnt] = v; sz[cnt] = 1;
root[w] = Merge(root[w],cnt);
}
};

int main(){
using namespace Skew_Heap;