VJ 传送门 https://vjudge.net/problem/CodeChef-MGCHGYM
简化题意: 给定一个长度为 \(N\) 的数列,\(Q\) 个操作:
\(1\,x\,a\), 将数列中第 \(x\) 个元素改为 \(a\)
\(2\,l\,r\), 反转子序列 \([l,r]\)
\(3\,l\,r\,w\), 询问区间 \([l,r]\) 中是否存在若干个数和为 \(w\), 一个数只能取一次
注意: 在整个过程中, 在数列中出现过的数的种数不会超过 \(K(K \leq 10)\).
注意到最后一个条件很奇怪......
考虑询问实际上是: 最开始给出不超过 \(10\) 个数 \(a_1,...,a_{10}\), 每一次给出 \(a_1,...,a_{10}\) 分别最多能够取的次数, 问是否能够取出若干使得和为 \(w\); 而前两个操作只是在改变这个能够取的最多次数.
不妨更进一步想, 试着求能够取的方案数......
是不是想到了......
HAOI2008 硬币购物 https://lydsy.com/JudgeOnline/problem.php?id=1042
那么我们可以直接按照硬币购物的方法去做
先用 \(a_1\) 到 \(a_{10}\) 跑完全背包, 对于每一次询问进行容斥, 强制令某一些数字超出使用次数并计算答案. 那么每一次询问的复杂度是 \(2^{10}\) 的.
最后使用 \(Splay\) 维护一下前两个修改操作, 题目就做完了.
? 关于完全背包存不下那么多方案数的问题...... 直接模 \(10^9+7\)
- #include<bits/stdc++.h>
- #define lch Tree[x].ch[0]
- #define rch Tree[x].ch[1]
- #define root Tree[0].ch[0]
- //This code is written by Itst
- using namespace std;
- inline int read(){
- int a = 0;
- char c = getchar();
- bool f = 0;
- while(!isdigit(c) && c != EOF){
- if(c == '-')
- f = 1;
- c = getchar();
- }
- if(c == EOF)
- exit(0);
- while(isdigit(c)){
- a = a * 10 + c - 48;
- c = getchar();
- }
- return f ? -a : a;
- }
- const int MAXN = 1e5 + 10 , MOD = 1e9 + 7;
- int dp[MAXN] , dir[11] , *cnt , N , Q , cntN , cntL;
- map <int , int> lsh;
- struct node{
- int ch[2] , sz , fa , val , sum[11];
- bool mark;
- }Tree[MAXN];
- struct query{
- int ind , a , b , c;
- }que[MAXN];
- inline int getL(int x){
- if(!lsh.count(x)){
- lsh[x] = ++cntL;
- dir[cntL] = x;
- }
- return lsh[x];
- }
- inline bool son(int x){
- return Tree[Tree[x].fa].ch[1] == x;
- }
- inline void pushup(int x){
- for(int i = 1 ; i <= 10 ; ++i)
- Tree[x].sum[i] = Tree[lch].sum[i] + Tree[rch].sum[i] + (Tree[x].val == i);
- Tree[x].sz = Tree[lch].sz + Tree[rch].sz + 1;
- }
- inline void rotate(int x){
- bool f = son(x);
- int y = Tree[x].fa , z = Tree[y].fa , w = Tree[x].ch[f ^ 1];
- Tree[x].fa = z;
- Tree[z].ch[son(y)] = x;
- Tree[x].ch[f ^ 1] = y;
- Tree[y].fa = x;
- Tree[y].ch[f] = w;
- if(w)
- Tree[w].fa = y;
- pushup(y);
- }
- inline void Splay(int x , int tar){
- while(Tree[x].fa != tar){
- if(Tree[Tree[x].fa].fa != tar)
- rotate(son(x) == son(Tree[x].fa) ? Tree[x].fa : x);
- rotate(x);
- }
- pushup(x);
- }
- inline void mark(int x){
- if(!x)
- return;
- swap(lch , rch);
- Tree[x].mark ^= 1;
- }
- inline void pushdown(int x){
- if(Tree[x].mark){
- mark(lch);
- mark(rch);
- Tree[x].mark = 0;
- }
- }
- void insert(int &x , int rk , int val , int fa){
- if(!x){
- x = ++cntN;
- Tree[x].fa = fa;
- Tree[x].sz = 1;
- Tree[x].val = val;
- Splay(x , 0);
- return;
- }
- if(Tree[lch].sz>= rk)
- insert(lch , rk , val , x);
- else
- insert(rch , rk - 1 - Tree[lch].sz , val , x);
- }
- void findKth(int x , int rk , int tar){
- pushdown(x);
- if(Tree[lch].sz == rk)
- Splay(x , tar);
- else
- if(Tree[lch].sz> rk)
- findKth(lch , rk , tar);
- else
- findKth(rch , rk - Tree[lch].sz - 1 , tar);
- }
- inline void modify(int x , int val){
- findKth(root , x , 0);
- --Tree[root].sum[Tree[root].val];
- ++Tree[root].sum[Tree[root].val = val];
- }
- inline void rev(int l , int r){
- findKth(root , l - 1 , 0);
- findKth(root , r + 1 , root);
- mark(Tree[Tree[root].ch[1]].ch[0]);
- }
- inline void query(int l , int r){
- findKth(root , l - 1 , 0);
- findKth(root , r + 1 , root);
- cnt = Tree[Tree[Tree[root].ch[1]].ch[0]].sum;
- }
- void init(){
- dp[0] = 1;
- for(int i = 1 ; i <= cntL ; ++i)
- for(int j = dir[i] ; j <= 1e5 ; ++j)
- dp[j] = (dp[j] + dp[j - dir[i]]) % MOD;
- }
- int dfs(int x , int sum , int flg){
- if(sum <0)
- return 0;
- if(x> cntL)
- return flg * dp[sum];
- return (dfs(x + 1 , sum , flg) + dfs(x + 1 , sum - (cnt[x] + 1) * dir[x] , flg * -1) + 1ll * MOD) % MOD;
- }
- int main(){
- #ifndef ONLINE_JUDGE
- freopen("in","r",stdin);
- freopen("out","w",stdout);
- #endif
- N = read();
- Q = read();
- insert(root , 0 , 0 , 0);
- for(int i = 1 ; i <= N ; ++i)
- insert(root , i , getL(read()) , 0);
- insert(root , N + 1 , 0 , 0);
- for(int i = 1 ; i <= Q ; ++i){
- que[i].ind = read();
- que[i].a = read();
- que[i].b = read();
- if(que[i].ind == 3)
- que[i].c = read();
- if(que[i].ind == 1)
- que[i].b = getL(que[i].b);
- }
- init();
- for(int i = 1 ; i <= Q ; ++i)
- switch(que[i].ind){
- case 1:
- modify(que[i].a , que[i].b);
- break;
- case 2:
- rev(que[i].a , que[i].b);
- break;
- case 3:
- query(que[i].a , que[i].b);
- puts(dfs(1 , que[i].c , 1) ? "Yes" : "No");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2936060.html