線段樹總結

線段樹總結—By Zach

本蒟蒻的總結僅供參考。。。

一、關於樹狀數組和線段樹

樹狀數組（二叉索引樹）：一般而言，用於序列滿足區間可減性、優先順序相同的運算中。例如，前綴和、差分、前綴異或和等等；程式碼短，易於調試，易擴展到二維；
zkw線段樹：一般而言，用於序列最值等二叉索引樹不能完成的帶修區間最值問題。注意：不可用於優先順序不同的修改！！相較於線段樹程式碼較短，易於調試；
線段樹：zkw能做的都能做，可以變身為可持續化線段樹。

二、典型套路總結

優先順序不同的運算

例題：[AHOI2009] 維護序列

我們考慮將整個操作轉化：先乘再加；

如果都是單一的兩種運算，延遲標記能做到這一點；那麼當兩者混合的時候，我們怎麼辦呢？

想像這樣一種情況：區間\([l,r]\)（原始序列），先乘了一個數\(x\)，再加上一個數\(y\)。那麼我們對於這樣的操作就是分別計算到延遲標記中，乘的那個數統計到乘法延遲標記當中，假髮一樣。

這時候這個區間又來了一個乘法（乘數記成\(z\)），那麼我們就應該先\(z*y\)，將加法延遲標記修改，再修改乘法延遲標記，進而修改到\(y*z\)。

也就是當進了一個加法操作，直接累加；進了一個乘法操作，修改加法延遲標記，再修改它本身的。

下放怎麼辦？我們可以將兩種運算分離，乘法先下放。這樣一來，我們把兩種優先順序不同的運算巧妙地合在了一起。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;

const int MAXN = 100000 + 5;

typedef long long LL;

int n, m;
LL mod;

struct Segment
{
	LL sum;
	LL flag_prob, flag_add;
	void init(LL val)
	{
		sum = val, flag_prob = 1, flag_add = 0;
	}
	inline void merge(Segment x, Segment y)
	{
		sum = (x.sum + y.sum) % mod, flag_prob = 1, flag_add = 0;
	}
} T[MAXN << 2];

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;	
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}
void spread(int p, int l, int r)
{
	if((T[p].flag_add || T[p].flag_prob != 1) && l != r)
	{	
		int mid = l + ((r - l) >> 1);
		T[p << 1].sum = 1ll * T[p << 1].sum * T[p].flag_prob % mod;
		T[p << 1].sum = (T[p << 1].sum + 1ll * (mid - l + 1) * T[p].flag_add % mod) % mod;
		T[p << 1 | 1].sum = 1ll * T[p << 1 | 1].sum * T[p].flag_prob % mod;
		T[p << 1 | 1].sum = (T[p << 1 | 1].sum + 1ll * (r - mid) * T[p].flag_add % mod) % mod;
		T[p << 1].flag_prob = 1ll * T[p << 1].flag_prob * T[p].flag_prob % mod;
		T[p << 1 | 1].flag_prob = 1ll * T[p << 1 | 1].flag_prob * T[p].flag_prob % mod;
		T[p << 1].flag_add = (1ll * T[p << 1].flag_add * T[p].flag_prob % mod + T[p].flag_add) % mod;
		T[p << 1 | 1].flag_add = (1ll * T[p << 1 | 1].flag_add * T[p].flag_prob % mod + T[p].flag_add) % mod;
	}
	T[p].flag_prob = 1, T[p].flag_add = 0;
	return;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		LL val;
		read(val);
		T[p].init(val % mod);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modify_I(int p, int l, int r, int L, int R, LL val)//����Ӳ��� 
{
	if(l >= L && r <= R)
	{
		T[p].sum = (T[p].sum + 1ll * (r - l + 1) * val % mod) % mod;
		T[p].flag_add = (T[p].flag_add + val) % mod;
		return;
	}
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify_I(lson, L, R, val);
	if(R > mid) modify_I(rson, L, R, val);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modify_II(int p, int l, int r, int L, int R, LL val)//����˲��� 
{
	if(l >= L && r <= R)
	{
		T[p].sum = 1ll * val * T[p].sum % mod;
		T[p].flag_add = 1ll * T[p].flag_add * val % mod;
		T[p].flag_prob = 1ll * T[p].flag_prob * val % mod;
		return;
	}
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify_II(lson, L, R, val);
	if(R > mid) modify_II(rson, L, R, val);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

LL query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum;
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	LL val = 0;
	if(L <= mid) val = (val + query(lson, L, R)) % mod;
	if(R > mid) val = (val + query(rson, L, R)) % mod; 
	return val;
}

int main()
{
	read(n), read(mod);
	build(wht);
	read(m);	
	int opt, l, r; 
	LL v;
	FOR(i, 1, m)
	{
		read(opt);
		read(l);
		read(r);
		if(opt == 1)
		{
			read(v);
			modify_II(wht, l, r, v);
		}
		else if(opt == 2)
		{
			read(v);
			modify_I(wht, l, r, v);
		}
		else printf("%lld\n", query(wht, l, r));
	}
	return 0;
}

最大子段和類問題

例題：小白逛公園

維護這樣幾個量：區間前綴最大值、後綴最大值、區間最大值、區間和。

區間最大值可以有各個區間的最大值或者左子區間的後綴最大值\(+\)右子區間的前綴最大值拼成。這樣一來，問題就解決了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define pii pair<int,int>
#define mp(x, y) make_pair(x,y)
using namespace std;

const int MAXN = 6e5 + 5, INF = 1e9;

typedef long long LL;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;	
	return;
}

struct Segment
{
	LL lmax, rmax, val_max, sum;
	void init(LL val)
	{
		lmax = rmax = val_max = sum = val;
	}
} T[MAXN << 2];

Segment operator +(Segment &x, Segment &y)
{
	Segment res;
	res.sum = x.sum + y.sum;
	res.lmax = max(x.lmax, x.sum + y.lmax), res.rmax = max(y.rmax, y.sum + x.rmax);
	res.val_max = max(max(x.val_max, y.val_max), max(max(res.lmax, res.rmax), x.rmax + y.lmax));
	return res;
}

int n, m;
void build(int p, int l, int r)
{
	if(l == r)
	{
		LL v;
		read(v), T[p].init(v);
		return;	
	}	
	int mid = l + ((r - l) >> 1); 
	build(lson), build(rson);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

void modify(int p, int l, int r, int pos, LL val)
{
	if(l == r)
	{
		T[p].init(val);
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modify(lson, pos, val); 
	else modify(rson, pos, val);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

Segment query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p];
	int mid = l + ((r - l) >> 1);
	Segment t1, t2;
	if(R <= mid) return query(lson, L, R);
	if(L > mid) return query(rson, L, R);
	t1 = query(lson, L, R), t2 = query(rson, L, R);
	return t1 + t2;
}

int main()
{
	read(n), read(m);
	build(wht);
	int k, a, b, p, s;
	FOR(i, 1, m)
	{
		read(k);
		if(k == 1)
		{
			read(a), read(b);
			if(a > b) swap(a, b);
			printf("%lld\n", query(wht, a, b).val_max);
		}
		else
		{
			read(p), read(s);
			modify(wht, p, s);
		}
	}
	return 0;
}

差分

例題：gcd區間

加強：區間修改。

題目看起來比較困難，但實際上通過推式子得到。

\[(x,y,z)=(x,y-x,z-y)
\]

由此可以曉得對於\(n\)元均成立。

這啟發我們用線段樹維護差分序列求\((x,y)\)，區間修改在差分序列中最轉化為單點修改。這樣一來，我們就將看似困難的問題解決了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

#define re register
#define U unsigned
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define wht 1,1,n
#define CLR(x,y) memset(x,y,sizeof(x))
#define FOR(i,x,y) for(re int i=x;i<=y;++i)
#define SFOR(i,u,v,w) for(re int i=u;i<=v;i+=w)
#define ROF(i,x,y) for(re int i=x;i>=y;--i)
#define SROF(i,u,v,w) for(re int i=u;i>=v;i-=w)
#define DEBUG(x) printf("Test#: %d\n", x)
using namespace std;

const int MAXN = 1000 + 5;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
}

int gcd(int x, int y)
{
	if(!y) return x;
	return gcd(y, x % y);
}

struct Segment
{
	int d;
	inline void init(int val)
	{
		d = abs(val);
		return;
	}
	inline void merge(Segment x, Segment y)
	{
		d = gcd(x.d, y.d);
		return;
	}
} T[MAXN << 2];

int n, m, a[MAXN];

void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].init(a[l] - a[l - 1]);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

int query(int p, int l, int r, int L, int R)
{
	if(r < L || l > R) return 1;
	if(l >= L && r <= R) return T[p].d;
	int mid = l + ((r - l) >> 1), val;
	if(L > mid) val = query(rson, L, R);
	else if(R <= mid) val = query(lson, L, R);
	else val = gcd(query(lson, L, R), query(rson, L, R));
	return val;
}

int main()
{
	read(n), read(m);
	a[0] = 0;
	FOR(i, 1, n) read(a[i]);
	build(wht);
	int L, R;
	while(m --)
	{
		read(L), read(R);
		if(L == R) printf("%d\n", a[L]);
		else printf("%d\n", gcd(a[L], query(wht, L + 1, R)));
	}
	return 0;
}

懶標記

例題：方差

區間加就區間加，平均數就是區間和類操作，方差怎麼辦？

考慮到：

\[\sum_{i=l}^r(a_i-a)^2/n=\sum_{i=l}^ra_i^2/n-a^2
\]

可以知道：平方和、求和均維護。

反觀加法，可以通過推式子分別維護。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;

const int N = 1e5 + 7;

typedef double db;
template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return; 
}
struct Segment
{
	db sum, prob, flag;
	void init(db val)
	{
		sum = val;
		prob = val * val;
		flag = 0;
	}	
} T[N << 2];

int n, m;
Segment operator +(Segment &x, Segment &y)
{
	Segment res;
	res.flag = 0;
	res.sum = x.sum + y.sum; 
	res.prob = x.prob + y.prob; 
	return res;
}

inline void spread(int p, int l, int r)
{
	if(T[p].flag && l != r)
	{
		int mid = l + ((r - l) >> 1);
		T[p << 1].flag += T[p].flag;
		T[p << 1].prob += T[p << 1].sum * T[p].flag * 2 + 1ll * (mid - l + 1) * T[p].flag * T[p].flag;
		T[p << 1].sum += 1ll * (mid - l + 1) * T[p].flag;
		T[p << 1 | 1].flag += T[p].flag;
		T[p << 1 | 1].prob += T[p << 1 | 1].sum * T[p].flag * 2 + 1ll * (r - mid) * T[p].flag * T[p].flag;
		T[p << 1 | 1].sum += 1ll * (r - mid) * T[p].flag;
	}
	T[p].flag = 0;
	return;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		db val;
		scanf("%lf", &val), T[p].init(val);		
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

void modify(int p, int l, int r, int L, int R, db val)
{
	if(l >= L && r <= R)
	{
		T[p].prob += T[p].sum * val * 2 + 1ll * (r - l + 1) * val * val;
		T[p].sum += 1ll * (r - l + 1) * val;
		T[p].flag += val;
		return;
	}
	int mid = l + ((r - l) >> 1);
	spread(p, l, r);
	if(L <= mid) modify(lson, L, R, val);
	if(R > mid) modify(rson, L, R, val);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

Segment query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p];
	spread(p, l, r);
	
	Segment res, tmp1, tmp2;
	int mid = l + ((r - l) >> 1);
	if(R <= mid) return query(lson, L, R);
	if(L > mid) return query(rson, L, R);
	tmp1 = query(lson, L, R), tmp2 = query(rson, L, R);
	res = tmp1 + tmp2;
	return res;
}

int main()
{
	read(n), read(m);
	build(wht);
	int op, x, y;
	db k;
	Segment tmp;
	FOR(i, 1, m)
	{
		read(op);
		if(op == 1)
		{
			read(x), read(y);
			scanf("%lf", &k);
			modify(wht, x, y, k);
		}
		else if(op == 2)
		{
			read(x), read(y);
			db res = query(wht, x, y).sum;
			printf("%.4lf\n", (double)res / (y - x + 1));
		} 
		else
		{ 
			read(x), read(y);
			tmp = query(wht, x, y);
			db sum = tmp.sum, prob = tmp.prob;
			int len = y - x + 1;
			printf("%.4lf\n", (double)(prob * len - sum * sum) / len / len);
		}
	}
	return 0;
}

例題：區間加區間sin和

_{lxl出的題，但很水。}

三角的和差公式。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;

const int N = 2e5 + 5;

typedef double db;
typedef long long LL;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true; 
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}

struct Segment
{
	LL flag;
	db sum_sin, sum_cos;	
	void init(LL val)
	{
		flag = 0, sum_sin = sin((db)val), sum_cos = cos((db)val);
	}
	void merge(Segment x, Segment y)
	{
		flag = 0;
		sum_sin = x.sum_sin + y.sum_sin;
		sum_cos = x.sum_cos + y.sum_cos;		
	}
} T[N << 2];

db sink, cosk;
int n, m;

void spread(int p, int l, int r)
{
	if(T[p].flag && l != r)
	{
		LL val = T[p].flag; db sin0, cos0;
		sin0 = T[p << 1].sum_sin, cos0 = T[p << 1].sum_cos;
		T[p << 1].flag += val, T[p << 1].sum_sin = sin0 * cos((db)val) + cos0 * sin((db)val), T[p << 1].sum_cos = cos0 * cos((db)val) - sin0 * sin((db)val);
		sin0 = T[p << 1 | 1].sum_sin, cos0 = T[p << 1 | 1].sum_cos;
		T[p << 1 | 1].flag += val, T[p << 1 | 1].sum_sin = sin0 * cos((db)val) + cos0 * sin((db)val), T[p << 1 | 1].sum_cos = cos0 * cos((db)val) - sin0 * sin((db)val);		
	}
	T[p].flag = 0;
	return;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		LL val;
		read(val);
		T[p].init(val);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
 	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modify(int p, int l, int r, int L, int R, int val)
{
	if(l >= L && r <= R)
	{
		T[p].flag += val;
		db sin0 = T[p].sum_sin, cos0 = T[p].sum_cos;
		T[p].sum_sin = sin0 * cosk + cos0 * sink, T[p].sum_cos = cos0 * cosk - sin0 * sink;
		return;
	}
	LL mid = l + ((r - l) >> 1);
	spread(p, l, r);
	if(L <= mid) modify(lson, L, R, val);
	if(R > mid) modify(rson, L, R, val);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

db query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum_sin;
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	db res = 0.00;
	if(L <= mid) res += query(lson, L, R);
	if(R > mid) res += query(rson, L, R);
	return res;
}

int main()
{
	read(n);
	build(wht);
	
	int opt, l, r, val;
	read(m);
	FOR(i, 1, m)
	{
		read(opt);
		if(opt == 1)
		{
			read(l), read(r), read(val);
			sink = sin(val);
			cosk = cos(val);
 			modify(wht, l, r, val);
		}
		else 
		{
			read(l), read(r);
 			printf("%.1lf\n", query(wht, l, r));
		}
	}
	return 0;
}

區間重複類

這一類問題常常有描述：區間數互不相同、存在數值相同的區間、存在兩個數值和是定值的區間

對於這一類問題，我們常常會對於每一個數值開一個\(set\)，在\(set\)里找前驅和後繼，線段樹維護前驅最大值，轉化為判斷區間最值。

例題：查找 Search

對於一個數，維護最大前驅；一個數，同時維護它的前驅（即與它相等的、在它前面的最大位置）

它的」互補前驅「（即與它和為給定值、在它前面的最大位置）它的後繼以及」互補「後繼。

更改的時候要同時對後繼更改。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>

#define fi first
#define se second
#define re register
#define U unsigned
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define wht 1,1,n
#define pii pair<int,int>
#define MP make_pair
#define CLR(x,y) memset(x,y,sizeof(x))
#define FOR(i,x,y) for(re int i=x;i<=y;++i)
#define SFOR(i,u,v,w) for(re int i=u;i<=v;i+=w)
#define ROF(i,x,y) for(re int i=x;i>=y;--i)
#define SROF(i,u,v,w) for(re int i=u;i>=v;i-=w)

using namespace std;

const int N = 5e5 + 5;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}

struct Segment
{
	int pre_max;
} T[N << 2];


set <int> table[N];

typedef set<int>::iterator iter;
int n, m, w, a[N], b[N];

void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].pre_max = 0;
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].pre_max = 0;
	return;
}

void modify(int p, int l, int r, int pos, int pre_val)//單點修改 
{
	if(l == r)
	{
		T[p].pre_max = pre_val;	
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modify(lson, pos, pre_val);
	else modify(rson, pos, pre_val);
	T[p].pre_max = max(T[p << 1].pre_max, T[p << 1 | 1].pre_max);
	return;
}

int query(int p, int l, int r, int L, int R)
{
	if(r < L || l > R) return 0;
	if(l >= L && r <= R) return T[p].pre_max;
	int mid = l + ((r - l) >> 1), val = 0;
	if(L <= mid) val = query(lson, L, R);
	if(R > mid) val = max(val, query(rson, L, R));
	return val;
}

int pre(int x)
{
	iter it1 = table[a[x]].lower_bound(x), it2 = table[w - a[x]].lower_bound(x);
	if(it2 == table[w - a[x]].begin()) return 0;
	else if(it1 == table[a[x]].begin()) return *--it2;
	else if(*--it1 > *--it2) return 0;
	return *it2;	
}
vector <int> res;
int main()
{
	read(n), read(m), read(w);
	FOR(i, 1, n) read(a[i]);
	build(wht);
	FOR(i, 1, n)
	{
		modify(wht, i, pre(i));	
		table[a[i]].insert(i);
	}
	int op, pos, val, l, r, cnt = 0;
	while(m --)
	{
		read(op);
		if(op == 1)
		{
			int pos, val;
			read(pos), read(val);// 修改5個量：pre1[pos] pre2[pos] nxt1[pos]相關 nxt2[pos]相關
			res.clear();
			// modify pos
			iter it1 = table[a[pos]].upper_bound(pos), it2 = table[w - a[pos]].lower_bound(pos);
			if(it1 != table[a[pos]].end()) res.push_back(*it1);
			if(it2 != table[w - a[pos]].end()) res.push_back(*it2);
			table[a[pos]].erase(pos);
			table[val].insert(pos), a[pos] = val;
			res.push_back(pos);
			it1 = table[a[pos]].upper_bound(pos), it2 = table[w - a[pos]].lower_bound(pos);
			if(it1 != table[a[pos]].end()) res.push_back(*it1);
			if(it2 != table[w - a[pos]].end()) res.push_back(*it2);
			for(int i = 0; i < res.size(); ++ i) modify(wht, res[i], pre(res[i]));
		}
		else
		{
			int l, r;
			read(l), read(r);
			l ^= cnt, r ^= cnt;
			if(query(wht, l, r) >= l) puts("Yes"), ++ cnt;
			else puts("No");
		}	
	}
	return 0;
}

例題：算術天才⑨與等差數列

形成等差數列的充要條件是：最大值和最小值範圍固定在某一段、區間兩兩數差的GCD為公差的倍數、元素不重複。

維護最大值和最小值，區間GCD（差分做法），和上述前驅做法。對於每一個出現的值開一個\(STL\) \(set\)。又要強制在線，直接開map求離散化。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath> 
#include<map>
#include<set>

#define Re register
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(Re int i=x;i<=y;++i)
#define SFOR(i, u, v, w) for(Re int i=u;i<=v;i+=w)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define DEBUG(x) printf("Test: %d\n", x) 

using namespace std;

const int MAXN = 3e5 + 5;

typedef set <int> ::iterator iter;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x; 
	return;
}

int gcd(int x, int y)
{
	if(!y) return x;
	return gcd(y, x % y);
}

map <int, int> table;
set <int> s[MAXN << 1];

int n, m, tot = 0, a[MAXN];

struct Segment
{
	int vmin, vmax, d, pre_max;
} T[MAXN << 2];

inline struct Segment merge(struct Segment x, struct Segment y)
{
	struct Segment p;
	p.vmax = max(x.vmax, y.vmax), p.vmin = min(x.vmin, y.vmin);
	p.d = gcd(x.d, y.d), p.pre_max = max(x.pre_max, y.pre_max);
	return p;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].vmax = T[p].vmin = a[l];
		T[p].d = abs(a[l] - a[l - 1]);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p] = merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modifyI(int p, int l, int r, int pos, int val) //修改區間最值 
{
	if(l == r)
	{
		T[p].vmax = T[p].vmin = val;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modifyI(lson, pos, val);
	else modifyI(rson, pos, val);
	T[p] = merge(T[p << 1], T[p << 1 | 1]); 
	return;	
}

void modifyII(int p, int l, int r, int pos, int val) //修改區間gcd 
{
	if(l == r)
	{
		T[p].d = abs(val);	
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modifyII(lson, pos, val);
	else modifyII(rson, pos, val);	
	T[p].d = gcd(T[p << 1].d, T[p << 1 | 1].d);
	return;
}

void modifyIII(int p, int l, int r, int pos, int val) // 修改區間最大前驅 
{
	if(l == r)
	{
		T[p].pre_max = val;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modifyIII(lson, pos, val);
	else modifyIII(rson, pos, val);
	T[p].pre_max = max(T[p << 1].pre_max, T[p << 1 | 1].pre_max);
	return;
}

Segment query(int p, int l, int r, int L, int R) // 區間最值 區間GCD pre_max 查詢 
{
	if(l >= L && r <= R) return T[p];
	int mid = l + ((r - l) >> 1);
	if(L > mid) return query(rson, L, R);
	if(R <= mid) return query(lson, L, R);
	Segment x = query(lson, L, R), y = query(rson, L, R);
	return merge(x, y);
}

int pre(int x)
{
	iter it = s[table[a[x]]].find(x);
	if(it == s[table[a[x]]].begin()) return 0; //沒有前驅 
	return (*--it);
}
int nxt(int x)
{
	iter it = s[table[a[x]]].find(x);
	if((++ it) == s[table[a[x]]].end()) return 0;
	return *it;
}

int main()
{
	read(n), read(m);
	a[0] = 0;
	FOR(i, 1, n) read(a[i]);
	FOR(i, 1, m + n) s[i].clear();
	build(wht);
	table.clear(), table[0] = 0;
	FOR(i, 1, n)
	{
		if(table.find(a[i]) == table.end()) table[a[i]] = ++ tot;
		s[table[a[i]]].insert(i);
		modifyIII(wht, i, pre(i));
	}
	int cnt = 0, op, x, y, l, r, k;
	FOR(i, 1, m)
	{
		read(op);
		if(op == 1)
		{
			read(x), read(y);
			x ^= cnt, y ^= cnt;
			if(table.find(y) == table.end()) table[y] = ++ tot;
			modifyI(wht, x, y);
			modifyII(wht, x, y - a[x - 1]), modifyII(wht, x + 1, a[x + 1] - y);
			int tmp = nxt(x);
			if(tmp) modifyIII(wht, tmp, pre(x));
			s[table[a[x]]].erase(x);
			s[table[a[x] = y]].insert(x);
			modifyIII(wht, x, pre(x));
			tmp = nxt(x);
			if(tmp) modifyIII(wht, tmp, x);
		}
		else
		{
			read(l), read(r), read(k);
			l ^= cnt, r ^= cnt, k ^= cnt;
			if(l == r) 
			{
				++ cnt, puts("Yes");
				continue;
			}
			Segment t1 = query(wht, l, r);
			if(k == 0) 
			{
				if(t1.vmax == t1.vmin) ++ cnt, puts("Yes");
				else puts("No");
				continue;
			}
			Segment t2 = query(wht, l + 1, r);
			if(t2.d % k == 0 && (t1.vmax - t1.vmin) == 1ll * k * (r - l) && t1.pre_max < l) 
				++ cnt, puts("Yes");
			else puts("No");
		}
	}
	return 0;	
} 

//solution:
/*  
詢問區間[l, r], 問該區間是否構成公差為 k 的等差數列 
1. 維護每個區間最大值, 最小值, VMAX-VMIN = (r - l)*k ;
2. 維護差分數組的gcd, 即當queryII(l+1,r)為k的倍數 時滿足; 
3. 保證區間內兩兩之間互不相等, 則預處理區間內 每個數的前驅在哪裡, 區間內前驅下標(queryIII(l+1,r))小於l才行
考慮到數的值比較大, 離散化一下(map!!!);
修改Ax=y: (單點修改) 
1. 單點修改區間最值
2. 差分b[x]=Ax-Ax-1, b[x+1]=Ax+1-Ax, 動態維護gcd;
3. 對於每一個值建一個set, 那麼對於Ax它的後繼要改, 前驅不變, 新的set後繼改, 前驅不變 
*/

非標記做法

這一類問題有一個特點：區間修改的操作無法進行延遲標記……

比方說，區間\(ln\)，對於每一個數向下取整（保證實數域有意義），區間和。會發現對於一個數，操作次數過多結果會一樣。只有前面的操作會影響維護的值，當該數減到\(0\)的時候不會再進行操作。因此，我們只需要記錄一下最大有效操作數即可，小於等於上限暴力修改，大於不管。很套路。

例題：上帝造題的七分鐘2

這道題對於區間開方。其實開多少次方題目無影響。

會發現一個數：\(\sqrt{\sqrt{ \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{…}}}}}}\)操作數有上限。

因此我們記錄操作數上限即可，不超過該數暴力修改，大於就置之不理。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define wht 1,1,n
using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5, INF = 1 << 30;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';	
	if(mark) x = -x;
	return;
}

struct Segment
{
	LL sum;
	int cnt;
	void init(LL val)
	{
		sum = val, cnt = 0;	
	} 
	void merge(Segment x, Segment y)
	{
		sum = x.sum + y.sum, cnt = min(x.cnt, y.cnt);
	}
} T[MAXN << 2];
int n, m, limit = 15;
void build(int p, int l, int r)
{
	if(l == r)
	{
		LL val;
		read(val);
		T[p].init(val);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}
void modify(int p, int l, int r, int L, int R)
{
	if(T[p].cnt >= limit) return;
	if(l == r)
	{
		T[p].sum = (int)sqrt(T[p].sum);
		++ T[p].cnt;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify(lson, L, R);
	if(R > mid) modify(rson, L, R);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}
LL Query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum;
	int mid = l + ((r - l) >> 1);
	LL res = 0;
	if(L <= mid) res += Query(lson, L, R);
	if(R > mid) res += Query(rson, L, R);
	return res;
}
int main()
{
	read(n);
	build(wht);
	read(m);	
	int opt, l, r;
	while(m --)
	{
		read(opt), read(l), read(r);
		if(l > r) swap(l, r);
		if(!opt) modify(wht, l, r);
		else printf("%lld\n", Query(wht, l, r));
	}
	return 0;
}

例題：[六省聯考 2017] 相逢是問候

很毒瘤！

這題居然和模數有了關係。

擴展歐拉定理：

\[a^b=a^{b\ mod\phi(n) +\phi(n)}(mod\ n)(b>=\phi(n))
\]

考慮不斷操作的過程，總會有一次\(\phi_{(…)}(p)=1\)，所以我們預處理出該有效次數。

但由於每一次都不是連續的（模數都不相同），所以我們不能直接像開方那樣直接操作。我們需要預處理出每次的操作次數下的答案。

由於擴展歐拉定理只能在指數大於模數的時候用，所以我們在處理的時候要記錄指數是否超過了模數，進行遞推。

但由於時間複雜度還是不夠，我們直接將\(c^a\)分解為\(c^{a\ mod\ 10000}*c^{a/10000}*c^{10000}\)數要與處理出來。

具體來說，我們可以定義一個遞推式：\(d[i,j,k]\)代表第\(i\)個數在進行到總共\(j\)次操作，當前處於\(\ mod\ \phi_{(k)}(p)\)階段，有：\(d[i,j,k]=c^{d[i,j-1,k+1]}\ mod\ \phi(k)\)。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(Re int i=x;i<=y;++i)
#define SFOR(i, u, v, w) for(Re int i=u;i<=v;i+=w)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define DEBUG(x) printf("Test: %d\n", x) 
using namespace std;

typedef long long LL;

const int MAXN = 5e4 + 5, MAX_lim = 30, SIZE = 1e4 + 5;

int euler(int x)
{
	int res = x;
	for(int i = 2; i <= sqrt(x); ++ i)
	{
		if(x % i == 0)
		{
			res = res / i * (i - 1);
			while(x % i == 0) x /= i;
		}
		if(x == 1) return res;
	}
	if(x > 1) res = res / x * (x - 1);
	return res;
}

struct Segment
{
	int cnt, sum;
} T[MAXN << 2];

bool b1[MAX_lim][SIZE] = {}, b2[MAX_lim][SIZE] = {}, bd[MAXN][MAX_lim][MAX_lim] = {};
int n, m, mod, c, lim = 0, a[MAXN], phi[MAX_lim];
LL pow1[MAX_lim][SIZE], pow2[MAX_lim][SIZE], d[MAXN][MAX_lim][MAX_lim];

Segment merge(Segment s, Segment t)
{
	Segment x;
	x.cnt = min(s.cnt, t.cnt), x.sum = (s.sum + t.sum) % mod;
	return x;
}
void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].cnt = 0, T[p].sum = a[l] % mod;
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p] = merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void prework()
{	
	phi[0] = mod;
	while(phi[lim ++] > 1) phi[lim] = euler(phi[lim - 1]);
	phi[lim] = 1;
	FOR(i, 0, lim)
	{
		pow1[i][0] = 1;
		FOR(j, 1, 10000)
		{
			pow1[i][j] = 1ll * pow1[i][j - 1] * c;
			if(pow1[i][j] >= phi[i]) pow1[i][j] %= phi[i], b1[i][j] = 1;
			b1[i][j] |= b1[i][j - 1];			
		}
	}
	FOR(i, 0, lim)
	{
		pow2[i][0] = 1;
		b2[i][1] = b1[i][10000];
		FOR(j, 1, 10000)
		{
			pow2[i][j] = 1ll * pow2[i][j - 1] * pow1[i][10000];
			if(pow2[i][j] >= phi[i]) pow2[i][j] %= phi[i], b2[i][j] = 1;
			b2[i][j] |= b2[i][j - 1] | b1[i][10000];
		}
	}
	FOR(i, 1, n)
	{
		FOR(j, 0, lim)
		{
			d[i][0][j] = a[i] % phi[j];
			if(a[i] >= phi[j]) bd[i][0][j] = 1;
		}
		FOR(j, 1, lim)
		{
			d[i][j][lim] = 0;
			FOR(k, 0, lim - 1)
			{
				d[i][j][k] = 1ll * pow2[k][d[i][j - 1][k + 1] / 10000] * pow1[k][d[i][j - 1][k + 1] % 10000];
				bd[i][j][k] = b1[k][d[i][j - 1][k + 1] % 10000] | b2[k][d[i][j - 1][k + 1] / 10000];
				if(d[i][j][k] >= phi[k]) d[i][j][k] %= phi[k], bd[i][j][k] |= 1;
				if(bd[i][j - 1][k + 1])
				{
					d[i][j][k] *= pow2[k][phi[k + 1] / 10000];					
					if(d[i][j][k] >= phi[k]) d[i][j][k] %= phi[k], bd[i][j][k] = 1;
					d[i][j][k] *= pow1[k][phi[k + 1] % 10000];
					if(d[i][j][k] >= phi[k]) d[i][j][k] %= phi[k], bd[i][j][k] = 1;
					bd[i][j][k] |= b1[j][phi[k + 1] % 10000] | b2[j][phi[k + 1] / 10000];
				}
			}
		}
	}
	return;
}

void modify(int p, int l, int r, int L, int R)
{
	if(T[p].cnt >= lim) return;
	if(l == r)
	{
		++ T[p].cnt;
		T[p].sum = d[l][T[p].cnt][0] % mod;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify(lson, L, R);
	if(R > mid) modify(rson, L, R);
	T[p] = merge(T[p << 1], T[p << 1 | 1]);
	return;
}

int query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum % mod;
	int mid = l + ((r - l) >> 1), val = 0;	
	if(L <= mid) val = query(lson, L, R) % mod;
	if(R > mid) val = (val + query(rson, L, R)) % mod;
	return val;
}

int main()
{
	scanf("%d %d %d %d", &n, &m, &mod, &c);
	FOR(i, 1, n) scanf("%d", &a[i]);
	prework();
	build(wht);
	int op, l, r;
	FOR(i, 1, m)
	{
		scanf("%d %d %d", &op, &l, &r);	
		if(!op) modify(wht, l, r);
		else printf("%d\n", query(wht, l, r));
	}
	return 0;
}

Tags: 數據結構數據結構—樹狀數組和線段樹