自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:03:42，当前版本为作者最后更新于2024-09-10 20:08:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

异或就是个很烦的东西，所以第一步是把异或处理掉。来拆一下条件：

• 递增且前缀异或和递增。说明异或的过程中最高位只能不断增加，所以最高位的位置严格递增。
• 后缀异或和递增。说明异或时不会有任何一个数的最高位被异或为 $0$。

于是可以得到等价充要条件：

一个数列是好的，当且仅当这些数的最高位所在的位单调递增，且这些位上均存在奇数个 $1$。

这个条件的形式已经足够简洁，可以支持我们对此进行计数。下文 $m\gets m+1$ 将限制变为 $<m$。

显然对于任意正整数 $n$，有 $\sum_{2\mid i}\binom ni=\sum_{2\nmid i}\binom ni=2^{n-1}$。相信这个大家都会证明。假设我们已经将所有最高位填完了，设 $a_i=2^{b_i}$，那么再往里面填 $1$ 的方案数是多少呢？可以发现：

若这一层有某个数的最高位，则这一行只能再偶数个。 否则，这一行可以随便填。

容易发现，当我们拆位后，每一位上填的方案数是好算的。设填之前 $0$ 的个数为 $c_0$，$1$ 的个数为 $c_1$，则方案数是 $2^{c_0-c_1}$。全部乘起来，特判下最后一个数的最高位，得到答案为 $2^{\sum b_i-n+1}$。
考虑单次询问怎么做。将 $m$ 拆成若干个值域段。设 $m=2^{k_1}+2^{k_2}+\cdots+2^{k_t}$，其中 $k_1>k_2>\cdots>k_t\ge0$，则拆成：

$$[0,2^{k_1}),[2^{k_1},2^{k_1}+2^{k_2}),\cdots,[m-2^{k_t},m) $$

这样 $m$ 的低位都在 $[0,2^k)$ 的范围内滑动。继续看倒数第二个数的最高位能在哪。假设当前枚举的值域段到了 $m$ 从高往低的第 $i$ 个 $1$：

• 最高位可以是 $m$ 已经被固定的 $0$。
• 最高位可以在 $a_i$，然后最后一个数的这一位不能是 $1$。

第二类情况恰好扣除一半，直接按照前面的公式计算。问题变成快速计算下面这个东西：

定义整数序列 $a$ 的权值为 $2^{\sum a_i}$，求所有递增且值域为 $[1,m]$ 的序列 $a$ 的权值和。

显然能暴力 dp，时间复杂度 $O(n^2)$，可以通过前 $2$ 个子任务，搭配数据结构维护可以通过前 $3$ 个子任务。

继续优化。严格递增是坏的，所以考虑 $a'_i=a_i-i$ 变成非严格递增，就能转化为格路计数问题。将 $a'$ 与 $n\times(m-n)$ 的网格上的格路建立映射：在第 $i$ 格前先向上走到 $a'_i$ 的位置。问题变为所有从左下到右上的路径右下部分面积的 $2$ 次幂之和。

对面积拆贡献。若在高度为 $h$ 的位置有一条向右走的边，那么这条边会对面积贡献 $h$，而 $h$ 的值其实就是这条边之前向上的边数。考虑把格路转化为 $0/1$ 串将向上的边标为 $1$，向右的边标为 $0$，则面积为该序列的逆序对个数。

可重串的逆序对是难以刻画的，但是我们可以用排列的逆序对来刻画 $0/1$ 串的逆序对。具体地，假设长度为 $K$ 的排列权值为 $f(K)$，那么对于一个长度为 $N+M$，$0,1$ 数量各为 $N,M$ 的 $0/1$ 串，其权值可以通过“将其视作排列的权值”除去 $0,1$ 内部的贡献来计算，也即 $\frac{f(N+M)}{f(N)f(M)}$。

对于长度为 $K$ 的排列，我们可以考虑递推。我们在序列末尾插入数时，可以不考虑在排列的某个位置插入，而是在值域上插入一个数。那么插入 $0,1,\cdots,K$ 会产生的逆序对数就与之前的排列无关了，为 $K,K-1,\cdots,0$。所以造成的贡献为 $2^K+2^{K-1}+\cdots+2^0=2^{K+1}-1$，即 $f(K+1)=(2^{K+1}-1)f(K)$。

化简至此容易做到 $O(n)-O(1)$，可以通过前 $4$ 个子任务，实现精细可以通过前 $5$ 个子任务。

接下来考虑如何处理多组询问。将 $m$ 划分成若干个 $0/1$ 段，每次操作都只会造成 $O(1)$ 个段的改动。然后对于连续 $0$ 段和 $1$ 段，都可以计算其贡献，$0$ 对其后的 $1$ 贡献，$1$ 对前面的 $0$ 贡献。考虑拿两个平衡树，分别维护 $0$ 与 $1$ 的连续段。段内求和都是好算的，段外只要实现前、后缀和即可。

总的时间复杂度是 $O(n+q\log q)$，常数取决于你怎么维护。可以通过所有子任务。想清楚的话实现还是较为简单的。

当然也可以用线段树维护，不过笔者并没有考虑到线段树做法。如果空间被卡的出题人在这谢罪了。

#include <bits/stdc++.h>

using namespace std;

#define dIO_USE_BUFFER
struct IO{
#ifdef dIO_USE_BUFFER
const static int BUFSIZE=1<<20;char ibuf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;inline int getchar(){return(p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}inline int putchar(char x){return((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++),x;}inline IO&flush(){return fwrite(obuf,1,pp-obuf,stdout),pp=obuf,fflush(stdout),*this;}IO(){p1=p2=ibuf,pp=obuf;}~IO(){flush();}
#else
int(*getchar)()=&::getchar;int(*putchar)(int)=&::putchar;inline IO&flush(){return fflush(stdout),*this;}
#endif
string _sep=" ";int k=2;template<typename Tp,typename enable_if<is_integral<Tp>::value||is_same<Tp,__int128_t>::value>::type* =nullptr>inline int read(Tp&s){int f=1,ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF)f=(ch=='-'?-1:1),ch=getchar();if(ch==EOF)return false;while(ch=='0')ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();s*=f;return true;}template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1,ch=getchar();s=0;while(!isdigit(ch)&&ch!='.'&&ch!=EOF)f=(ch=='-'?-1:1),ch=getchar();if(ch==EOF)return false;while(isdigit(ch))s=s*10+(ch^48),ch=getchar();if(ch=='.'){Tp eps=0.1;ch=getchar();while(isdigit(ch))s=s+(ch^48)*eps,ch=getchar(),eps/=10;}s*=f;return true;}inline int read(char&ch){ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();return ch!=EOF;}inline int read(char*c){char ch=getchar(),*s=c;while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)*(c++)=ch,ch=getchar();*c='\0';return s!=c;}inline int read(string&s){s.clear();char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)s+=ch,ch=getchar();return s.size()>0;}template<typename Tp=int>inline Tp read(){Tp x;read(x);return x;}template<typename Tp,typename...Ts>inline int read(Tp&x,Ts&...val){return read(x)&&read(val...);}inline int getline(char*c,const char&ed='\n'){char ch=getchar(),*s=c;while(ch!=ed&&ch!=EOF)*(c++)=ch,ch=getchar();*c='\0';return s!=c;}inline int getline(string&s,const char&ed='\n'){s.clear();char ch=getchar();while(ch!=ed&&ch!=EOF)s+=ch,ch=getchar();return s.size()>0;}template<typename Tp,typename enable_if<is_integral<Tp>::value||is_same<Tp,__int128_t>::value>::type* =nullptr>inline IO&write(Tp x){if(x<0)putchar('-'),x=-x;static char sta[41];int top=0;do sta[top++]=x%10^48,x/=10;while(x);while(top)putchar(sta[--top]);return*this;}inline IO&write(const string&str){for(char ch:str)putchar(ch);return*this;}inline IO&write(const char*str){while(*str!='\0')putchar(*(str++));return*this;}inline IO&write(char*str){return write((const char*)str);}inline IO&write(const char&ch){return putchar(ch),*this;}template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline IO&write(Tp x){if(x>1e18||x<-1e18){write("[Floating point overflow]");throw;}if(x<0)putchar('-'),x=-x;const static long long pow10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,100000000000000000,100000000000000000};const auto&n=pow10[k];long long whole=x;double tmp=(x-whole)*n;long long frac=tmp;double diff=tmp-frac;if(diff>0.5){++frac;if(frac>=n)frac=0,++whole;}else if(diff==0.5&&((frac==0U)||(frac&1U)))++frac;write(whole);if(k==0U){diff=x-whole;if((!(diff<0.5)||(diff>0.5))&&(whole&1))++whole;}else{putchar('.');static char sta[21];int count=k,top=0;while(frac){sta[top++]=frac%10^48;frac/=10,count--;}while(count--)putchar('0');while(top)putchar(sta[--top]);}return*this;}template<typename Tp,typename...Ts>inline IO&write(Tp x,Ts...val){return write(x),write(_sep),write(val...),*this;}template<typename...Ts>inline IO&writeln(Ts...val){return write(val...),putchar('\n'),*this;}template<typename...Ts>inline IO&writesp(Ts...val){return write(val...),putchar(' '),*this;}inline IO&writeln(void){return putchar('\n'),*this;}inline IO&sep(const string&s=" "){return _sep=s,*this;}inline IO&prec(const int&K=2){return k=K,*this;}}io;

typedef long long ll;
typedef unsigned uint;

const int MAXN = 1e6 + 10;
const int MAXM = 1e7 + 30;
const int mod = 998244353;

inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }
inline int del(int x, int y) { return x -= y, x < 0 ? x + mod : x; }

inline 
int qpow(int b, int p) {
	int res = 1;
	for (; p; p >>= 1, b = (ll)b * b % mod) if (p & 1) res = (ll)res * b % mod;
	return res;
}

int p[MAXM], p2[MAXM], pp2[MAXM];

int q_fac[MAXM], q_ifac[MAXM];

inline 
void init(int n) {
	for (int i = 1; i <= n; i++) p[i] = add(p[i - 1], p[i - 1] + 1);
	*p2 = 1;
	for (int i = 1; i <= n; i++) p2[i] = add(p2[i - 1], p2[i - 1]);
	*pp2 = 1;
	for (int i = 1; i <= n; i++) pp2[i] = (ll)pp2[i - 1] * p2[i - 1] % mod;
	*q_fac = 1;
	for (int i = 1; i < n; i++) q_fac[i] = (ll)q_fac[i - 1] * p[i] % mod;
	q_ifac[n - 1] = qpow(q_fac[n - 1], mod - 2);
	for (int i = n - 1; i; i--) q_ifac[i - 1] = (ll)q_ifac[i] * p[i] % mod;
}

inline 
int q_binom(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return (ll)q_fac[n] * q_ifac[m] % mod * q_ifac[n - m] % mod;
}

inline 
int f(int n, int m) {
	return (ll)q_binom(n, m) * pp2[m - 1] % mod;
}

mt19937 eng(time(0));

struct FHQ_treap {
	
	struct node {
		int ls, rs, size; uint w;
		int l, r; int val, sum;
		node(int l = 0, int r = 0, int val = 0) : 
			ls(0), rs(0), size(1), w(eng()), 
			l(l), r(r), val(val), sum(val) {} 
	} t[MAXN]; int cnt = 0, rt = 0;
	
	node operator [] (int k) const { return t[k]; }
	
	inline 
	int create(int l, int r, int val) {
		return t[++cnt] = node(l, r, val), cnt;
	}
	
	inline 
	void pushup(int p) {
		t[p].size = t[t[p].ls].size + t[t[p].rs].size + 1;
		t[p].sum = add(add(t[t[p].ls].sum, t[t[p].rs].sum), t[p].val);
	}
	
	void split(int p, int k, int &x, int &y) {
		if (!p) return x = y = 0, void();
		if (t[p].r <= k) x = p, split(t[p].rs, k, t[p].rs, y);
		else y = p, split(t[p].ls, k, x, t[p].ls); pushup(p);
	}
	
	int merge(int x, int y) {
		if (!x || !y) return x | y;
		if (t[x].w < t[y].w) return t[x].rs = merge(t[x].rs, y), pushup(x), x;
		return t[y].ls = merge(x, t[y].ls), pushup(y), y;
	}
	
	inline 
	void insert(int l, int r, int val) {
		int ls, rs; split(rt, r, ls, rs);
		rt = merge(merge(ls, create(l, r, val)), rs);
	}
	
	inline 
	void erase(int k) {
		int ls, rs, p; split(rt, k, ls, rs), split(ls, k - 1, ls, p);
		rt = merge(merge(ls, merge(t[p].ls, t[p].rs)), rs);
	}
	
	inline 
	int ask(int k, bool f) {
		int ls, rs, ans; split(rt, k, ls, rs);
		ans = f ? t[rs].sum : t[ls].sum, rt = merge(ls, rs);
		return ans;
	}
	
	inline 
	int prev(int k) {
		int ls, rs, p; split(rt, k - 1, ls, rs);
		for (p = ls; t[p].rs; p = t[p].rs);
		return rt = merge(ls, rs), p;
	}
	
	inline 
	int next(int k) {
		int ls, rs, p; split(rt, k, ls, rs);
		for (p = rs; t[p].ls; p = t[p].ls);
		return rt = merge(ls, rs), p;
	}
	
	inline 
	int qmax() {
		int p = rt;
		for (; t[p].rs; p = t[p].rs);
		return t[p].r;
	}
	
};

FHQ_treap t0, t1; int ans = 0, n;

inline 
int calc_0(int l, int r) {
	return del(f(r + 1, n - 1), f(l, n - 1));
}

inline 
int calc_1_x(int l, int r) {
	return del(p2[r + 1], p2[l]);
}

inline 
int calc_1_y(int l, int r) {
	int res = (ll)p2[r] * f(r + 1, n - 1) % mod;
	if (l) res = del(res, (ll)p2[l - 1] * f(l, n - 1) % mod);
	return res;
}

inline 
void insert_0(int l, int r) {
	int x = calc_0(l, r); ans = add(ans, (ll)x * t1.ask(l - 1, 0) % mod);
	int p = t0.prev(r), q = t0.next(r);
	assert(!p || t0[p].r < l), assert(!q || t0[q].l > r);
	if (p && t0[p].r == l - 1) l = t0[p].l, t0.erase(t0[p].r);
	if (q && t0[q].l == r + 1) r = t0[q].r, t0.erase(t0[q].r);
	t0.insert(l, r, calc_0(l, r));
}

inline 
void erase_0(int l, int r) {
	int x = calc_0(l, r); ans = del(ans, (ll)x * t1.ask(l - 1, 0) % mod);
	int k = t0.next(r - 1);
	int pl = t0[k].l, pr = t0[k].r; t0.erase(pr);
	if (l > pl) t0.insert(pl, l - 1, calc_0(pl, l - 1));
	if (r < pr) t0.insert(r + 1, pr, calc_0(r + 1, pr));
}

inline 
void insert_1(int l, int r) {
	int x = calc_1_x(l, r), y = calc_1_y(l, r);
	ans = add(ans, add((ll)x * t0.ask(r, 1) % mod, y));
	int p = t1.prev(r), q = t1.next(r);
	assert(!p || t1[p].r < l), assert(!q || t1[q].l > r);
	if (p && t1[p].r == l - 1) l = t1[p].l, t1.erase(t1[p].r);
	if (q && t1[q].l == r + 1) r = t1[q].r, t1.erase(t1[q].r);
	t1.insert(l, r, calc_1_x(l, r));
}

inline 
void erase_1(int l, int r) {
	int x = calc_1_x(l, r), y = calc_1_y(l, r);
	ans = del(ans, add((ll)x * t0.ask(r, 1) % mod, y));
	int k = t1.next(r - 1);
	int pl = t1[k].l, pr = t1[k].r; t1.erase(pr);
	if (l > pl) t1.insert(pl, l - 1, calc_1_x(pl, l - 1));
	if (r < pr) t1.insert(r + 1, pr, calc_1_x(r + 1, pr));
}

inline 
void add(int x) {
	int k0 = t0.next(x - 1), k1 = t1.next(x - 1);
	int l0 = t0[k0].l, r0 = t0[k0].r, l1 = t1[k1].l, r1 = t1[k1].r;
	if (k0 && l0 <= x && x <= r0) erase_0(x, x), insert_1(x, x);
	else if (k1 && l1 <= x && x <= r1) {
		erase_1(x, r1), insert_0(x, r1);
		if (k0) erase_0(r1 + 1, r1 + 1); insert_1(r1 + 1, r1 + 1);
	} else {
		k1 = t1.prev(x), r1 = t1[k1].r;
		insert_1(x, x); if (r1 < x - 1) insert_0(r1 + 1, x - 1);
	}
}

inline 
void del(int x) {
	int k0 = t0.next(x - 1), k1 = t1.next(x - 1);
	int l0 = t0[k0].l, r0 = t0[k0].r, l1 = t1[k1].l, r1 = t1[k1].r;
	if (k1 && l1 <= x && x <= r1) {
		erase_1(x, x), r1 = t1.qmax();
		if (r1 < x - 1) erase_0(r1 + 1, x - 1); else insert_0(x, x); 
	} else if (k0 && l0 <= x && x <= r0) {
		erase_0(x, r0), insert_1(x, r0);
		erase_1(r0 + 1, r0 + 1), r1 = t1.qmax();
		if (r1 > r0) insert_0(r0 + 1, r0 + 1);
	}
}

inline 
int query() {
	int r1 = t1.qmax();
	return add(del(ans, calc_1_y(r1, r1)), f(r1, n));
}

int q;

int main() {
	io.read(n, q), init(1e7 + 30), insert_1(0, 0);
	for (int x, opt; q--;) {
		io.read(opt);
		if (opt == 0) io.read(x), add(x);
		else if (opt == 1) io.read(x), del(x);
		else io.writeln(query());
	}
}

其实 $O(n^2)\to O(n)$ 的优化是一个叫做 q-analog 的普及度还算高科技，但是主播在完全不知道这个的情况下研发出了本题做法（甚至是快讲评的时候才知道的），导致完全没料想到这个组合意义会被直接秒……如果影响到大家的比赛体验也在这里磕头了。