11.12 NOIP云斗模拟赛

, , , , ,

包含口胡成分。

T4 离散化写错调了 1h 没调出来。这种低级错误能不能少一点啊啊啊！

T1

https://yundouxueyuan.com/p/5289?tid=654477590123557c779ff907

容易发现合法的点的子树大小一定 $\ge \dfrac{n}{2}$，而这些点在树上形成一条链。

省事的话可以二分做到 $O(n\log n)$。感觉应该有实现好的 $O(n)$ 做法。

代码没写。

T2

https://yundouxueyuan.com/p/5292?tid=654477590123557c779ff907

感觉就是二分要删除的区间的大小，然后贪心放 $0$ 即可。

代码没写。

T3

https://yundouxueyuan.com/p/5288?tid=654477590123557c779ff907

如果 $n=1$ 的话，考虑数位 dp，记录 dp 到第 $i$ 位，当前模 $m$ 的值，是否顶到上界，这一位是 $0/1$。

现在 $n$ 不为 $1$ 了，发现 $n$ 很小，状压是否顶到第 $i$ 个数的上界，按低位到高位转移。

递推转移，初值要把所有是否顶到上界的状态都设为 $1$。

复杂度 $O(nm2^n\log w)$ ，应该还有一个 $4$ 的常数。感觉出题人脑子坏掉了出毫无意义的卡常题目。

放下被卡的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,a[25];
const int base=31;
int f[2][16][21][(1<<15)+5][2];
void add(int &x,int y) {(x+=y)>=mod&&(x-=mod);}
signed main(void){
//	freopen("sample5.in","r",stdin);
	int i,j,k,l,s;
	read(n);read(m);
	int N=(1<<n);
	for (i=0;i<n;i++) read(a[i]);
	for (s=0;s<N;s++) f[0][n-1][0][s][0]=1;
	for (k=1;k<=base;k++) {//第k位
		int now=k&1,pre=now^1;
		memset(f[now],0,sizeof(f[now]));
		int tmp=(1<<k-1)%m;
		for (i=0;i<n;i++) {//第i个数
			int nums=(a[i]>>k-1)%2;
			for (j=0;j<m;j++) {//模m=j
				for (s=0;s<N;s++) {//是否顶到上界
					int lim=(s>>i)&1;
					for (l=0;l<=(lim?nums:1);l++) {
						int t=s;
						if (lim&&l!=nums) t^=(1ll<<i);//更新状态
						if (s<t) return 1;
						if (i==0) {
							add(f[now][i][j][s][l],f[pre][n-1][(j-l*tmp+m)%m][t][0]);
							add(f[now][i][j][s][l],f[pre][n-1][(j-l*tmp+m)%m][t][1]);
						}//如果是第一个数，则从上一层转移
						else {
							add(f[now][i][j][s][l],f[now][i-1][(j-l*tmp+m)%m][t][0]);
							add(f[now][i][j][s][1^l],f[now][i-1][(j+l*tmp+m)%m][t][1]);
						}//否则从这一层的上一个数转移
					}
				}
			}
		}
		
	}
	printf("%d",f[base&1][n-1][0][N-1][0]);
	return 0;
}

T4

赛后发现离散化的时候数组下标位置写错了。哈哈。

观察

显然先把 $b\gets \max(b,100)$。不取 $a$ 的原因是 $a$ 可能会变。

从手玩一下 $n=2,n=3$ 的情况，发现 $a,b$ 独立且 $a,b$ 分别从小到大排完序以后，答案为 $\sum \max(a_i,b_i)$。具体感觉可以数学归纳一下。

维护

因为跟顺序没关系，考虑放到值域上考虑。先观察值域很小的点。

令 $na_i=\sum [a_j\ge i],nb_i=\sum [a_j\ge i]$ ，在值 $i$ 的贡献为 $\max{na_i,nb_i}$。

感觉这样子就容易很多了麻！我们的操作有区间加，查询全局的贡献和。每个 $na_i$ 关于操作一定是单调不降的，也就是只会超过 $nb_i$ 一次。维护差的最小值然后暴力更新就好了。

值域更大的情况可以离散化。复杂度 $O((n+q)\log n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 600005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int a[maxn],b[maxn],c[maxn],n,q;
int g[maxn],tot,d[maxn],ans;
pair<int,int>e[maxn];
struct yyy {
	int Min,siz,lazy,tag,sum,id;
	yyy(int a=0,int b=0,int c=0,int d=0,int e=0,int f=0) {
		Min=a,siz=b,lazy=c,tag=d,sum=e,id=f;
	}
}f[maxn<<2];
void pushup(int rt) {
	f[rt].Min=min(f[rt<<1].Min,f[rt<<1|1].Min);
	if (f[rt].Min==f[rt<<1].Min) f[rt].id=f[rt<<1].id;
	else f[rt].id=f[rt<<1|1].id;
	f[rt].siz=f[rt<<1].siz+f[rt<<1|1].siz;
	f[rt].sum=f[rt<<1].sum+f[rt<<1|1].sum;
}
void pushdown(int rt) {
	if (f[rt].lazy) {
		int k=f[rt].lazy;f[rt].lazy=0;
		f[rt<<1].sum+=k*f[rt<<1].siz,f[rt<<1|1].sum+=k*f[rt<<1|1].siz;
		f[rt<<1].lazy+=k,f[rt<<1|1].lazy+=k;
	}
	if (f[rt].tag) {
		int k=f[rt].tag;f[rt].tag=0;
		f[rt<<1].Min+=k,f[rt<<1|1].Min+=k;
		f[rt<<1].tag+=k,f[rt<<1|1].tag+=k;
	}
}
const int inf=1e9;
void Update(int l,int r,int rt,int head,int tail,yyy k) {	
	if (head<=l&&r<=tail) {
		if (k.Min) f[rt].Min=inf;
		if (k.siz) f[rt].siz+=k.siz;
		if (k.lazy) f[rt].lazy+=k.lazy,f[rt].sum+=f[rt].siz*k.lazy;
		if (k.tag) f[rt].Min+=k.tag,f[rt].tag+=k.tag;
		return ;
	}
	pushdown(rt);
	int mid=l+r>>1;
	if (head<=mid) Update(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,k);
	pushup(rt);
}
void Build(int l,int r,int rt) {
	if (l==r) {
		f[rt].Min=d[l];
		f[rt].id=l;
		return ;
	}
	int mid=l+r>>1;
	Build(l,mid,rt<<1);
	Build(mid+1,r,rt<<1|1);
	pushup(rt);
}
void check(void) {
	while (f[1].Min<0) {
		int id=f[1].id;
		Update(1,tot,1,id,id,yyy(inf,g[id]-g[id-1],1,0,0,0));
	}
}
int o[maxn];
signed main(void){
	int i;
	read(n);read(q);
	for (i=1;i<=n;i++) read(a[i]),c[i]=a[i],o[i]=c[i];
	for (i=1;i<=n;i++) read(b[i]),b[i]=max(b[i],100ll);
	for (i=1;i<=n;i++) g[++tot]=a[i],g[++tot]=b[i];
	for (i=1;i<=q;i++) {
		read(e[i].fi),read(e[i].se);
		c[e[i].fi]+=e[i].se;
		g[++tot]=c[e[i].fi];
	}
	sort(g+1,g+1+tot);
	tot=unique(g+1,g+1+tot)-g-1;
	for (i=1;i<=n;i++) {
		ans+=b[i];
		a[i]=lower_bound(g+1,g+1+tot,a[i])-g;
		b[i]=lower_bound(g+1,g+1+tot,b[i])-g;
		d[b[i]]++;
	}
	for (i=tot;i>=1;i--) d[i]+=d[i+1];
	Build(1,tot,1);
	for (i=1;i<=n;i++) {
		Update(1,tot,1,1,a[i],yyy(0,0,1,-1,0,0));
		check();
	}
	printf("%lld\n",f[1].sum+ans);
	for (i=1;i<=q;i++) {
		int tmpl=lower_bound(g+1,g+1+tot,o[e[i].fi])-g;
		o[e[i].fi]+=e[i].se;
		int tmp=lower_bound(g+1,g+1+tot,o[e[i].fi])-g;
		Update(1,tot,1,tmpl+1,tmp,yyy(0,0,1,-1,0,0));
		check();
		printf("%lld\n",f[1].sum+ans);
	}
	return 0;
}