题意翻译（原题义太难懂了）

每一次操作都选中一个值为$0$的数，可以选择将他改为$-1$或是将他和他左边的连续$0$串都改为$i$。

两个数列不同，即从左到右第$i$个出现的不同颜色，将他设为$i$（后续证明均基于此），最后得到两个序列至少有一位不同。

例子：在重新编号（上一段所说）后可能会得到以下数列（仅为例子方便理解）：$1,1,1,2,2,3,4,4,4,5,0,0,-1,1,\dots$

证明

经过昨天激烈的四人帮真理标准大讨论，我也是成功的没能打出动态开点线段树。我深刻反思一整晚，想到了$3^n$的更简单的解释：每个点只有三个选择，留着后面的数给他涂，自己涂成正数，自己涂成$-1$。就这么简单。

当然，如果你想吃屎追求上进，可以看一下我赛时的想法。

首先考虑$n$位最后都变为正数的情况，考虑构造差分数组，第$2$~$n$位都可以是$0$或$1$，每一种方案都合法，故总共有$2^{n-1}$种方式。

然后，如果加入$0$，不难发现$0$一定在末尾，枚举剩余正数的个数，再计算全为$0$的情况，故方案数变为$\sum_{i=1}^{n}{2^{i-1}}+1$，即$2^n$。

最后，考虑加入$-1$的情况。由于$-1$只能在$a_i=0$的位置加入，先后顺序与答案无关，不妨设所有$-1$都在最开始加入。

先考虑最简单的情况：只有一个$-1$的情况。不难发现此时数组变为了$x$个$0$，一个$-1$，$n-x-1$个$0$，两边的方案数乘起来就是$2^x\times2^{n-x-1}$，即$2^{n-1}$。同理易得有$i$个$-1$时（$0\leq i\leq n$），方案数为$2^{n-i}$。

最后将所有$-1$的出现位置方案数乘上剩余非负数方案数，加和即为最终答案，具体式子如下：

$$\sum_{i=0}^{n}{C_n^i\times 2^{n-i}}$$

由于本蒟蒻对数学不太熟悉，没认出这就是二项式定理，卡了五分钟，最后是hansang发现的。原式等于$3^n$。

补充：二项式定理

$$(a+b)^n=\sum_{i=0}^{n}{C_n^i\times a^i\times b^{n-i}}$$

上述证明中取$a=1$，$b=2$

大家好，我非常不喜欢动态开点线段树，所以我用离散化解决了这道题。

其余部分不再赘述，解法就是将用一个数来代表一个区间，然后就写完了，优势在空间极小。（亲测为动态开点线段树的十分之一）

代码：

#include<bits/stdc++.h>
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
const int mod=1e9+7;
struct que{
	long long l,r;
};
que qu[100005];
bool tag[1600050];
long long bj[200005];
long long qul[400010];
long long qur[400010];
long long tr[1600050];
long long power(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1){
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
long long len(int l,int r){
	return qur[r]-qul[l]+1;
}
void up(int root){
	tr[root]=tr[ls(root)]+tr[rs(root)];
}
void down(int root,int l,int r){
	if(tag[root]){
		int mid=(l+r)>>1;
		tag[ls(root)]^=1;
		tr[ls(root)]=len(l,mid)-tr[ls(root)];
		tag[rs(root)]^=1;
		tr[rs(root)]=len(mid+1,r)-tr[rs(root)];
		tag[root]=0;
	}
}
void build(int root,int l,int r){
	if(l==r){
		tr[root]=len(l,r);
		return;
	}
	int mid=(l+r)>>1;
	build(ls(root),l,mid);
	build(rs(root),mid+1,r);
	up(root);
}
void change(int root,int l,int r,int x,int y){
	if(x<=l && r<=y){
		tag[root]^=1;
		tr[root]=len(l,r)-tr[root];
		return;
	}
	down(root,l,r);
	int mid=(l+r)>>1;
	if(x<=mid){
		change(ls(root),l,mid,x,y);
	}
	if(y>mid){
		change(rs(root),mid+1,r,x,y);
	}
	up(root);
}
int main(){
	long long n,q;
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		cin>>qu[i].l>>qu[i].r;
		bj[i*2-1]=qu[i].l;
		bj[i*2]=qu[i].r;
	}
	bj[q*2+1]=1;
	bj[q*2+2]=n;
	sort(bj+1,bj+2*q+3);
	int s=unique(bj+1,bj+2*q+3)-bj-1;
	int ji=0;
	for(int i=1;i<=s;i++){
		ji++;
		qul[ji]=qur[ji]=bj[i];
		if(bj[i+1]-bj[i]>1 && i<s){
			ji++;
			qul[ji]=bj[i]+1;
			qur[ji]=bj[i+1]-1;
		}
	}
	build(1,1,ji);
	for(int i=1;i<=q;i++){
		int x=lower_bound(qul+1,qul+ji+1,qu[i].l)-qul;
		int y=lower_bound(qur+1,qur+ji+1,qu[i].r)-qur;
		change(1,1,ji,x,y);
		cout<<power(3,tr[1])<<"\n";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 15e6 + 10;
const LL P = 1e9 + 7;
int a[N];
 
LL q_pow(LL a, LL b) {
		LL c = 1;
	while (b) {
		if (b & 1) {
			c = c * a % P;
		}
		a = a * a % P; 
		b >>= 1;
	}
	return c;
}
 
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
 
struct node {
	int ls, rs;
	LL siz;
	int lazy;
} tr[N];
int rt, trlen;
LL n;
 
void newd(int &p, LL L, LL R) {
	trlen ++; p = trlen;
	tr[p] = {0, 0, R - L + 1, 0};
}
 
void pushup(int p) {
	tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz;
}
 
void pushdown(int p, LL L, LL R) {
	if (tr[p].lazy) {
		
		LL mid = (L + R) >> 1;
		if (!lc(p)) {
			newd(lc(p), L, mid);
		}
		if (!rc(p)) {
			newd(rc(p), mid + 1, R);
		}
		
		tr[lc(p)].lazy ^= 1;
		
		tr[lc(p)].siz = (mid - L + 1) - tr[lc(p)].siz;
		
		tr[rc(p)].lazy ^= 1;
		
		tr[rc(p)].siz = (R - (mid + 1) + 1) - tr[rc(p)].siz;
		
		tr[p].lazy = 0;
	}
}
 
void change(int &p, LL L, LL R, LL l, LL r) {
	if (!p) {
		newd(p, L, R);
	}
	if (r < L || R < l) {
		return ;
	}
	if (l <= L && R <= r) {
		tr[p].siz = (R - L + 1) - tr[p].siz;
		tr[p].lazy ^= 1;
		return ; 
	}
	LL mid = (L + R) >> 1;
	pushdown(p, L, R);
	change(lc(p), L, mid, l, r);
	change(rc(p), mid + 1, R, l, r);
	pushup(p);
}
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int q;
	cin >> n >> q;
	trlen = 0; rt = 0;
	while (q --) {
		LL l, r;
		cin >> l >> r;
		change(rt, 1ll, n, l, r);
		cout << q_pow(3, tr[rt].siz) << "\n";
	}
	
	return 0;
} 

不知道多久前模拟赛考过的题，补一下。

这个答案最后应该要写成一个好维护的形式，所以考虑怎么化简。

显然每一个连续的 $0$ 构成的段中方案数是互不影响的，所以只需要每一段根别考虑即可。

先考虑要选几个 $0$ 变为 $-1$，假设总共有 $x$ 个 $0$，其中选择 $y$ 个变为 $-1$，这个方案数显然为 $\binom{x}{y}$。

接下来考虑 $0$ 的方案数，因为变为 $-1$ 的已经选过了，所以对于每个剩下的 $0$，只有以下 $2$ 种操作：

1. 不管它，让后面的 $0$ 来改变它的值。
2. 选中并进行一次操作 $2$。

对于每个 $0$ 都有 $2$ 种操作可选，所以方案数为 $2^x$。

与前面的方案数结合到一起，可以得到答案为 $\displaystyle{\sum_{y=0}^{x}\binom{x}{y}2^{x-y}}$，使用二项式定理化简得到 $3^x$。

这个东西是容易维护的，直接动态开点线段树即可。

代码有需要注意细节，尤其其数据类型和数组大小，我因为这个调了快 $1$ 个晚自习。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1.7e7 + 5;
const int mod = 1e9 + 7;
ll n;
int q;
ll qpow(ll x, ll y)
{
    ll res = 1;
    while(y)
    {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
struct Seg
{
    ll sum0[N];
    bool lazy[N];
    int ls[N], rs[N];
    int tot;
    int newSeg(ll l)
    {
        tot++;
        sum0[tot] = l;
        lazy[tot] = 0;
        ls[tot] = rs[tot] = 0;
        return tot;
    }
    void pushup(int p)
    {
        sum0[p] = sum0[ls[p]] + sum0[rs[p]];
        return;
    }
    void pushdown(int p, ll l, ll r)
    {
        if(!lazy[p]) return;
        ll mid = l + r >> 1;        
        sum0[ls[p]] = mid - l + 1 - sum0[ls[p]];
        lazy[ls[p]] ^= 1;
        sum0[rs[p]] = r - mid - sum0[rs[p]];
        lazy[rs[p]] ^= 1;
        lazy[p] = 0;
        return;
    }
    void flip(int p, ll l, ll r, ll ql, ll qr)
    {
        if(ql <= l && r <= qr)
        {
            sum0[p] = r - l + 1 - sum0[p];
            lazy[p] ^= 1;
            return;
        }
        ll mid = l + r >> 1;
        if(!ls[p]) ls[p] = newSeg(mid - l + 1);
        if(!rs[p]) rs[p] = newSeg(r - mid);
        pushdown(p, l, r);
        if(ql <= mid) flip(ls[p], l, mid, ql, qr);
        if(qr > mid) flip(rs[p], mid + 1, r, ql, qr);
        pushup(p);
        return;
    }
    void init(ll _x)
    {
        tot = 0;
        newSeg(_x);
        return;
    }
}tr;
int main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
    cin >> n >> q;
    tr.init(n);
    while(q--)
    {
        ll l, r;
        cin >> l >> r;
        tr.flip(1, 1, n, l, r);
        cout << qpow(3, tr.sum0[1]) << "\n";
    }
    return 0;
}

::::

结论与证明

答案为 $3^c \pmod{10^9+7}$ ，其中 $c$ 为当前序列中 0 的个数。

设序列长度为 $n$，全部为 0。由于最终结果允许对正整数颜色任意重标号（双射），操作顺序不影响等价类，我们可以从左到右依次对每个 0 进行决策。

对于每一个 0，恰好有 3 种本质不同的选择：

1.这段从未被正向颜色触碰

2.被某个正向颜色完整覆盖

3.被某个正向颜色部分覆盖

因此全 0 序列的方案数 = $3^n$。

$-1$ 是不可着色的，它将序列分割成若干极长连续的 0 段。各段之间操作互不影响且正整数颜色可跨段自由重标号。

故各段方案数相乘。设第 $i$ 段长度为 $\ell_i$，则：

$$K = \prod_i 3^{\ell_i} = 3^{\sum \ell_i} = 3^{c}$$

其中 $c = \sum \ell_i$ 即为序列中 0 的总个数 。

算法实现

问题转化为：维护一个 0/-1 序列，支持区间取反，查询 0 的个数。

$N \leq 10^{18}$ 无法直接建树，但 $Q \leq 10^5$。于是可以收集所有 $L_i,\ R_i+1$，离散化后得到压缩数组 tmp[1..m]。相邻两点构成一个压缩段，段内状态一致，原始长度为 tmp[i+1] - tmp[i]。

对 $m$ 个数字建线段树，每个节点维护：

• tr[p]：该区间内 0 的原始长度之和（即 0 的个数）
• tag[p]：懒标记，表示是否需要翻转

每次操作后，根节点 tr[1] 即为 $c$，则答案为 $3^c \mod (10^9+7)$。

此代码的时间复杂度为 $O(QlogN)$。

AC代码

#include<bits/stdc++.h>
#define int long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
constexpr int N=2e5+10,P=1e9+7;
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=a*a%P)
		if(b&1)
			res=res*a%P;
	return res;
}
int n,m,tmp[N],Q,tr[N<<2];
bool tag[N<<2];
pair<int,int>qry[N];
inline void pushup(int p,int l,int r){
	tag[p]^=1;
	tr[p]=tmp[r+1]-tmp[l]-tr[p];
}
inline void pushdown(int p,int l,int r){
	int mid=l+r>>1;
	if(tag[p]){
		pushup(ls(p),l,mid);
        pushup(rs(p),mid+1,r);
        tag[p]=0;
    }
}
inline void change(int p,int l,int r,int x,int y){
	if(x>r||y<l)return;
	if(x<=l&&y>=r){
		pushup(p,l,r);
		return;
	}
	int mid=l+r>>1;
	pushdown(p,l,r);
	change(ls(p),l,mid,x,y);
	change(rs(p),mid+1,r,x,y);
	tr[p]=tr[ls(p)]+tr[rs(p)];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>Q;
	m=2;
	tmp[1]=0;
	tmp[2]=n+1;
	int u,v;
	for(int i=1;i<=Q;i++){
		cin>>u>>v;
		qry[i]={u,v};
		tmp[++m]=u;
		tmp[++m]=v+1;
	}
	sort(tmp+1,tmp+m+1);
	m=unique(tmp+1,tmp+m+1)-tmp-1;
	for(int i=1;i<=Q;i++){
		int l=lower_bound(tmp+1,tmp+m+1,qry[i].first)-tmp,r=upper_bound(tmp+1,tmp+m+1,qry[i].second)-tmp-1;
		change(1,1,m,l,r);
		cout<<qpow(3,n-tr[1])<<"\n";
	}
}