H - Yuuki and a problem
题目 题意大概是 ： 给一个数组，有两种操作： 1 x y 把x位置上的值替换为y 2 l r 求 l ~ r 区间内元素任意子集的和都不能构成的最小值。 这个题刚开始看到，没有一点想法，， 后来也没一点想法。。 如果只有查询怎么办？ 只有查询的话，我只能想到背包。再次感慨我好菜 对，就是背包的想法。 如果把1 ~ x 内的数都能由他的子集表示出来，那么x + 1满足什么条件才能表示出来？ 在1 ~ x 的数都能表示出来的前提下，1 ~ x + 1 内数的和如果大于等于x + 1，那么x + 1就能被表示出来。 为什么呢？可以试想一下背包，0 ~ x 内dp值全为1 那么只要随便有一个1 ~ x + 1的数 就可以转移过来了。所以成立。 如果x + 1能表示出来，后面的同理， 所以可得： 如果1 ~ x能表示出来，则直接跳到（区间在1 ~ x内数的和） + 1就可以了。 这个最低时间复杂度情况下是一个Fibonacci数列。所以查询不了几次。很快。 那么全是查询，没有修改的情况可以用主席树里的查询来完成。 现在多了一个修改，怎么办？ 树状数组套线段树来写。
代码：
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <map>
#include <bitset>
#include <math.h>
#include <set>
#include <ctime>
#include <unordered_set>
#include <climits>
using namespace std
;
typedef long long ll
;
typedef pair
<int,ll
> pii
;
typedef pair
<ll
,ll
> pll
;
typedef pair
<double,double> pdd
;
typedef unsigned long long ull
;
typedef unordered_set
<int>::iterator sit
;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){freopen("P3380_2.in","r",stdin);freopen("hash.out","w",stdout);}
ll
gcd(ll a
,ll b
){return b
== 0 ? a
: gcd(b
,a
% b
);}
ll
qpow(ll a
,ll b
,ll mod
){a
%= mod
;ll ans
= 1;while(b
> 0){if(b
& 1)ans
= ans
* a
% mod
;a
= a
* a
% mod
;b
>>= 1;}return ans
% mod
;}
struct cmp
{bool operator()(const pii
& a
, const pii
& b
){return a
.second
> b
.second
;}};
int lb(int x
){return x
& -x
;}
const int inf
= INT_MAX
;
const double esp
= 1e-9;
const ll INF
= 0x3f3f3f3f3f3f;
const ll mod
= 1e9+7;
const int maxn
= 4e5 + 5;
const int M
= 3e5+5;
struct Node
{
int l
,r
;
ll sum
;
}node
[maxn
* 40];
int root
[maxn
];
int cnt
= 0;
int n
;
int tree
[maxn
];
void build(int l
,int r
,int pos
,int& no
,int num
)
{
if(no
== 0)
no
= ++cnt
;
node
[no
].sum
+= num
;
if(l
== r
)
return;
int mid
= l
+ r
>> 1;
if(pos
<= mid
)
build(l
,mid
,pos
,node
[no
].l
,num
);
else
build(mid
+ 1,r
,pos
,node
[no
].r
,num
);
}
ll
query(int l
,int r
,int lq
,int rq
,int no
)
{
if(no
== 0)
return 0;
if(l
> rq
|| r
< lq
)
return 0;
if(l
>= lq
&& r
<= rq
)
return node
[no
].sum
;
int mid
= l
+ r
>> 1;
return query(l
,mid
,lq
,rq
,node
[no
].l
) + query(mid
+ 1,r
,lq
,rq
,node
[no
].r
);
}
void add(int x
,int pos
,int num
)
{
while(x
<= n
)
{
build(1,n
,pos
,root
[x
],num
);
x
+= lb(x
);
}
}
ll
ask(int x
,int l
,int r
)
{
ll ans
= 0;
while(x
)
{
ans
+= query(1,n
,l
,r
,root
[x
]);
x
-= lb(x
);
}
return ans
;
}
int a
[maxn
];
int main()
{
int m
;
scanf("%d%d",&n
,&m
);
for (int i
= 1; i
<= n
; i
++ )
scanf("%d",&a
[i
]);
for (int i
= 1;i
<= n
; i
++ )
add(i
,a
[i
],a
[i
]);
while(m
-- )
{
int f
,x
,y
;
scanf("%d%d%d",&f
,&x
,&y
);
if(f
== 1)
{
add(x
,a
[x
],-a
[x
]);
add(x
,y
,y
);
a
[x
] = y
;
}
else
{
ll s1
= ask(y
,1,1);
ll s2
= ask(x
- 1,1,1);
if(s1
- s2
== 0)
{
printf("1\n");
continue;
}
ll p
= 2;
while(1)
{
ll s1
= ask(y
,1,min(p
,1ll * n
));
ll s2
= ask(x
- 1,1,min(p
,1ll * n
));
if(s1
- s2
< p
)
break;
p
= s1
- s2
+ 1;
}
printf("%lld\n",p
);
}
}
}
（好短的树套树），如果想到了，代码应该不会有太大的问题。 但是想不到解法呀。。 我好菜
