2019 ICPC Asia Xuzhou Regional H.Yuuki and a problem
题目链接
https://nanti.jisuanke.com/t/42547
题目大意
给你一个长度为 $n$ 的数列 $a_i$ ， $q$ 次询问，每次修改一个数的值，或者询问区间 $[l, r]$ 中所有的数所不能组出来的最小的正整数。
题目分析
不大清楚这题标程咋写的为啥要 $15s$（现场是 $12s$？）……个人认为 $O(n\log^2n)$ 的算法还是比较明显的。
首先如果 $[1, x]$ 中的所有数都可以被组出来，那么对于任何一个 $y \leq x + 1$，都可以使 $[1, x + y]$ 中的所有的数被组出来。
这样显然如果维护查询区间的有序数列，只需要前缀扫一遍就可以得到答案了。但是如果这样用线段树维护的话显然复杂度还是很大。
可以发现有了上面这个结论了之后，显然一个数列可以分为若干个区间，每个区间表示如果这个区间最小的数可以被组成了，那么剩下的数也可以对答案产生贡献。也就是说每隔区间需要记录两个数据，一个是最小的数 $x$，一个是这个区间的总和 $sum$。两个区间 $(x_1, sum_1), (x_2, sum_2), x_1 \leq x_2$ 能合并当且仅当 $x_1 + sum_1 >= x_2$，合并后的新区间即为 $(x_1, sum_1 + sum_2)$。由于 $x \leq sum$ ，所以连个相邻的区间的最小值最少相差两倍，所以可以证明这些区间的数量是 $\log n$ 级别的。
这样就可以直接搞了，代码很短不难写，而且题目数据不强，一开始我的代码合并的时候判的是 $sum_1 + 1 >= x_2$ 也只跑了 $9493ms$，而事实上这样写区间的数量可以被卡到 $O(n)$ 级别，是不满足复杂度要求的。改为 $x_1 + sum_1 >= x_2$ 之后就只用了 $2093ms$。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
long long a[maxn];
struct ex {
vector <pair <long long ,long long> > vec;
int init(long long x){
vec.clear();
vec.push_back(make_pair(x, x));
return 0;
}
};
ex merge(ex x, ex y){
ex ret;
ex tmp;
tmp.vec.resize(x.vec.size() + y.vec.size());
merge(x.vec.begin(), x.vec.end(), y.vec.begin(), y.vec.end(), tmp.vec.begin());
ret.vec.push_back(tmp.vec[0]);
for(int i=1;i<tmp.vec.size();i++){
pair <long long, long long> p = tmp.vec[i];
if(ret.vec.back().second + ret.vec.back().first >= p.first){
ret.vec.back().second += p.second;
}else{
ret.vec.push_back(p);
}
}
return ret;
}
struct stnode {
int l, r;
int lc, rc;
ex inf;
};
struct st {
stnode tree[maxn * 4];
int tc;
int root;
int init_tree(int l, int r){
int mid = (l + r) / 2;
int pos = ++tc;
tree[pos].l = l;
tree[pos].r = r;
if(l == r){
tree[pos].inf.init(a[l]);
return pos;
}
tree[pos].lc = init_tree(l, mid);
tree[pos].rc = init_tree(mid + 1, r);
tree[pos].inf = merge(tree[tree[pos].lc].inf, tree[tree[pos].rc].inf);
return pos;
}
ex query_tree(int pos, int l, int r){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l == l and r == tree[pos].r){
return tree[pos].inf;
}else{
if(r <= mid){
return query_tree(tree[pos].lc, l, r);
}else if(l <= mid){
return merge(query_tree(tree[pos].lc, l, mid), query_tree(tree[pos].rc, mid + 1, r));
}else{
return query_tree(tree[pos].rc, l, r);
}
}
}
int update_tree(int pos, int p, long long x){
int mid = (tree[pos].l + tree[pos].r) / 2;
if(tree[pos].l == tree[pos].r){
tree[pos].inf.init(x);
}else{
if(p <= mid){
update_tree(tree[pos].lc, p, x);
}else{
update_tree(tree[pos].rc, p, x);
}
tree[pos].inf = merge(tree[tree[pos].lc].inf, tree[tree[pos].rc].inf);
}
return 0;
}
long long query(int l, int r){
ex ret = query_tree(root, l, r);
if(ret.vec[0].first != 1)return 1;
return ret.vec[0].second + 1;
}
int update(int p, long long x){
update_tree(root, p, x);
return 0;
}
int init(int x){
int i, j;
tc = 0;
root = init_tree(1, x);
return 0;
}
} tree;
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
int x, y;
int opt;
n = read();
m = read();
for(i=1;i<=n;i++){
a[i] = read();
}
tree.init(n);
while(m--){
opt = read();
x = read();
y = read();
if(opt == 1){
tree.update(x, y);
}else{
printf("%lld\n", tree.query(x, y));
}
}
return 0;
}