发篇题解证明我的博客园还活着......
前言
这道题的常规写法大概有：链表，线段树。
我做的时候什么也没想，就直接线段树干就完了.....因为我没有脑子......
但是实际上可以用链表做到复杂度 O((n)) 级别。
具体做法
- 1.线段树
线段树做法需要支持的操作为：
区间覆盖，单点修改，区间查询，单点查询。
这道题目的难点就在于怎么样维护水一直往下面流。那么我们可以想到二分来判断水会流满哪一些沙漏，然后对于这段区间实行区间覆盖，用一个前缀和（前缀和里面存的是容量的前缀和)） + 区间查询目前水量区间和来辅助二分。最后我们发现会剩下一点水无法注满下一个漏斗，然后采用单点修改，将水注入不能注满的沙漏即可即可。
对于询问就直接单点查值即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
char buf[1 << 22],*p1 = buf,*p2 = buf;
#define mid ((L[x] + R[x]) >> 1)
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin),p1 == p2) ? EOF: *p1++)
inline int read() {
int x = 0 , flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
typedef long long LL;
const int MAXN = 2e5 + 50;
int n,m;
int A[MAXN],S[MAXN];//A存容量，S存容量的前缀和
struct SegmentTree {
LL sum[MAXN << 2],laz[MAXN << 2],L[MAXN << 2],R[MAXN << 2];
void build(int x,int l,int r) {
sum[x] = laz[x] = 0;
L[x] = l , R[x] = r;
if(l == r) return ;
build(x << 1 , l , mid);
build(x << 1 | 1 , mid + 1 , r);
return ;
}
void ad(int x,LL k) {
laz[x] = 1;
sum[x] = S[R[x]] - S[L[x] - 1];//全部注满
return ;
}
void changepos(int x,int pos,int k) {
if(pos > n) return ;
if(L[x] == R[x] && L[x] == pos) {
sum[x] += k; return;
}
pushdown(x);
if(pos <= mid) changepos(x << 1 , pos , k);
if(pos > mid) changepos(x << 1 | 1 , pos , k);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
return ;
}
void change(int x,int l,int r,LL k) {
if(l > r) return ;
if(L[x] >= l && R[x] <= r) {
ad(x,k); return ;
}
if(l <= mid) change(x << 1 , l , r , k);
if(r > mid) change(x << 1 | 1 , l , r , k);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
return ;
}
void pushdown(int x) {//下传标记
if(laz[x] == 0) return ;
ad(x << 1 , laz[x]);
ad(x << 1 | 1 , laz[x]);laz[x] = 0;
return ;
}
int GetVal(int x,int l,int r) {
if( l > r) return 0;
int s = 0;
if(L[x] >= l && R[x] <= r) return sum[x];
pushdown(x);
if(l <= mid) s += GetVal(x << 1 , l , r);
if(r > mid) s += GetVal(x << 1 | 1 , l , r);
return s;
}
} T;
int check(int u,int val) {//二分找出可以注满的沙漏的区间右端点
int s = u - 1;//注意这个地方初值要写成u-1
for(int i = log2(n - u + 1) ; i >= 0 ; i --) {
int C = s + (1 << i);
if(C > n) continue;
if(val >= (S[C] - S[u - 1] - T.GetVal(1,u,C))) s += (1 << i);//二分
}
return s;
}
signed main() {
n = read();
for(int i = 1 ; i <= n ; i ++) A[i] = read(),S[i] = S[i - 1] + A[i];
m = read();
T.build(1 , 1 , n + 1);
while(m --) {
int op = read(),u,x;
if(op == 1) {
u = read() , x = read();
int l = u , r = check(u,x),val = x - (S[r] - S[l - 1] - T.GetVal(1,l,r));
//val代表的是剩下的水
T.change(1, l, r, 1);//区间覆盖
T.changepos(1,r + 1,val);//单点修改
}
else {
u = read();
cout << T.GetVal(1,u,u) << endl;
}
}
return 0;
}
- 链表
大概思路：
链表里存的是下一个没有被装满的水桶。初始值即为 (nxt[i] = i + 1)，当一个水桶被装满的时候，我们每次跳其(nxt[]) 即可，这样子跳下去，直到跳到水没了，然后再更新路径上的 (nxt) 数组。这个方法不难发现均摊下来是 O((n)) 的。代码短了不止一点点，快了不止亿点点。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
char buf[1 << 22],*p1 = buf,*p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin),p1 == p2) ? EOF: *p1++)
inline int read() {
int x = 0 , flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
typedef long long LL;
const int MAXN = 2e5 + 50;
int n,m;
int A[MAXN],nxt[MAXN],N[MAXN];
signed main() {
n = read();
for(int i = 1 ; i <= n ; i ++) A[i] = read(),nxt[i] = i + 1;
m = read();
while(m --) {
int op = read(),u,x;
if(op == 1) {
u = read() , x = read();
int now = u;
while(nxt[now]) {
if(x + N[now] >= A[now]) x -= (A[now] - N[now]), N[now] = A[now];
else {N[now] += x ; break;}
now = nxt[now];
}
int t;
while(u != now) t = u , u = nxt[u] , nxt[t] = now;
}
else {
u = read();
cout << N[u] << endl;
}
}
return 0;
}
总结
以后一定要动脑子思考问题，不要一上来就打暴力，这个习惯不好......