感觉自己虽然在学习树剖的时候学习了线段树（这什么学习过程？

但是感觉自己还有很多姿势不够

所以先做几道题吧

update20170112: 新增一道各种操作的题目：BZOJ1858

update20161108: 修修补补地到了10题

竟然才做了9道QAQ

连两位数都没上 羞耻.jpg

1012: [JSOI2008]最大数maxnumber

比较简单的线段树吧

也没有太复杂的标记什么的

真是简单粗暴

听说还有单调栈和单调队列的做法，真刺激

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define MM 200020
using namespace std;
char ch[10];
int mx[MM*4],a[MM];
int la,l,n,m,t,d,mm;
void change(int ll,int rr,int st)
{
	if (ll==rr)	{	mx[st]=n;	return;	}
	int mid=(ll+rr)/2;
	if (l<=mid) change(ll,mid,st<<1);
		else change(mid+1,rr,(st<<1)+1);
	mx[st]=max(mx[st<<1],mx[(st<<1)+1]);
	return;
}
int check(int ll,int rr,int l,int r,int st)
{
	if (ll<=l&&rr>=r) return mx[st];
	int sum=0,mid=(l+r)/2;
	if (ll<=mid) sum=max(sum,check(ll,rr,l,mid,st<<1));
	if (rr>mid) sum=max(sum,check(ll,rr,mid+1,r,(st<<1)+1));
	return sum;
}
int main()
{
	scanf("%d%d",&m,&d);
	t=l=0;
	mm=m;
	memset(mx,0,sizeof(mx));
	while (m--)
	{
		scanf("%s%d",&ch,&n);
		l++;
		if (ch[0]=='A')
		{
			a[++la]=l;	n=(n%d+t%d)%d;	change(1,mm,1);
		}
		else
		{	printf("%d\n",t=check(a[la-n+1],a[la],1,mm,1));
			t%=d;		}
	}
	return 0;
}

1798: [Ahoi2009]Seq 维护序列seq

其实和黈力上课讲的某一题差不多的吧

但标记不能永久化

要维护两个tag

调的累炸了

听说窝的程序跑得比xmc快？！（但人家的程序短啊！

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;

#define NN 100005
#define LL long long

struct Tree
{
	int l,r;
	LL t1,t2,sum;
}tr[NN<<2];
int n,m,mod,op,l,r,x,a[NN];

void Build(int p,int l,int r)
{
	tr[p].l = l, tr[p].r = r, tr[p].t1 = 0, tr[p].t2 = 1;
	if (l == r) { tr[p].sum = a[l] % mod; return; }
	int mid = (l+r) >> 1;
	Build(p<<1,l,mid); Build(p<<1|1,mid+1,r);
	tr[p].sum = (tr[p<<1].sum + tr[p<<1|1].sum) % mod;
}

void push_down(int num)  
{  
    if (tr[num].t2==1&&tr[num].t1==0) return;  
    tr[num*2].t1=(tr[num*2].t1*tr[num].t2+tr[num].t1)%mod;  
    tr[num*2+1].t1=(tr[num*2+1].t1*tr[num].t2+tr[num].t1)%mod;  
    tr[num*2].t2=(tr[num*2].t2*tr[num].t2)%mod;  
    tr[num*2+1].t2=(tr[num*2+1].t2*tr[num].t2)%mod;  
    tr[num*2].sum=(tr[num*2].sum*tr[num].t2+(tr[num*2].r-tr[num*2].l+1)*tr[num].t1)%mod;  
    tr[num*2+1].sum=(tr[num*2+1].sum*tr[num].t2+(tr[num*2+1].r-tr[num*2+1].l+1)*tr[num].t1)%mod;  
    tr[num].t1=0;  
    tr[num].t2=1;  
    return;  
}  

void mul(int p,int l,int r,int xx)
{
	if (tr[p].l > r || tr[p].r < l) return;
	if (tr[p].l >= l && tr[p].r <= r)
	{
		tr[p].t1 = tr[p].t1 * xx % mod;
		tr[p].t2 = tr[p].t2 * xx % mod;
		tr[p].sum = tr[p].sum * xx % mod;
		return;
	}
	push_down(p);
	mul(p<<1,l,r,xx); mul(p<<1|1,l,r,xx);
	tr[p].sum = (tr[p<<1].sum + tr[p<<1|1].sum) % mod;
	return;
}
void add(int p,int l,int r,int xx)
{
	if (tr[p].l > r || tr[p].r < l) return;
	if (tr[p].l >= l && tr[p].r <= r)
	{
		tr[p].t1 = (tr[p].t1 + xx) % mod;
		tr[p].sum = (tr[p].sum + (tr[p].r - tr[p].l + 1)*xx % mod) % mod;
		return;
	}
	push_down(p);
	add(p<<1,l,r,xx); add(p<<1|1,l,r,xx);
	tr[p].sum = (tr[p<<1].sum + tr[p<<1|1].sum) % mod;
	return;
}

LL query(int p,int l,int r)
{
	if (tr[p].l > r || tr[p].r < l) return 0;
	if (tr[p].l >= l && tr[p].r <= r) return tr[p].sum % mod;
	push_down(p);
	return (query(p<<1,l,r) + query(p<<1|1,l,r)) % mod;
}

int main()
{
	scanf("%d%d",&n,&mod);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	Build(1,1,n);
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d",&op);
		switch (op)
		{
			case 1:
				scanf("%d%d%d",&l,&r,&x);
				mul(1,l,r,x);
				break;
			case 2:
				scanf("%d%d%d",&l,&r,&x);
				add(1,l,r,x);
				break;
			case 3:
				scanf("%d%d",&l,&r);
				printf("%d\n",query(1,l,r)%mod);
				break;
		}
	}
	return 0;
}

3212: Pku3468 A Simple Problem with Integers

维护线段树，区间加，区间求和

注意long long

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;

#define LL long long
#define NN 100005

int n,m,x,y,z;
char ch[10];
struct Tree
{
	LL s,ad;
	int l,r;
}tr[NN<<2];

void push_up(int p)
{
	tr[p].s = tr[p<<1].s + tr[p<<1|1].s;
}

void push_down(int p)
{
	if (tr[p].l == tr[p].r) return;
	if (tr[p].ad)
	{
		tr[p<<1].ad += tr[p].ad, tr[p<<1|1].ad += tr[p].ad;
		tr[p<<1].s += tr[p].ad * (tr[p<<1].r - tr[p<<1].l + 1);
		tr[p<<1|1].s += tr[p].ad * (tr[p<<1|1].r - tr[p<<1|1].l + 1);
		tr[p].ad = 0;
	}
}

void Build(int p,int l,int r)
{
	tr[p].l = l, tr[p].r = r;
	if (l == r) { scanf("%lld",&tr[p].s); return;}
	int mid = (l+r) >> 1;
	Build(p<<1,l,mid); Build(p<<1|1,mid+1,r);
	push_up(p);
}

void Add(int p,int L,int R,int v)
{
	push_down(p);
	int l = tr[p].l, r = tr[p].r, sum = (r-l+1), mid = (l+r) >> 1;
	if (l == L && R == r) { tr[p].s += (LL) v * sum, tr[p].ad += v; return;	}
	if (mid >= R) Add(p<<1,L,R,v);
	else if (mid < L) Add(p<<1|1,L,R,v);
	else Add(p<<1,L,mid,v), Add(p<<1|1,mid+1,R,v);
	push_up(p);
}

LL Query(int p,int L,int R)
{
	push_down(p);
	int l = tr[p].l, r = tr[p].r, mid = (l+r) >> 1;
	if (l == L && R == r) return tr[p].s;
	if (mid >= R) return Query(p<<1,L,R);
	else if (mid < L) return Query(p<<1|1,L,R);
	else return Query(p<<1,L,mid) + Query(p<<1|1,mid+1,R);
}

int main()
{
	scanf("%d%d",&n,&m);
	Build(1,1,n);
	while (m--)
	{
		scanf("%s",ch);
		if (ch[0] == 'Q')
		{
			scanf("%d%d",&x,&y);
			printf("%lld\n",Query(1,x,y));
		}
		else
		{
			scanf("%d%d%d",&x,&y,&z);
			Add(1,x,y,z);
		}
	}
	return 0;
}

3226: [Sdoi2008]校门外的区间

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

char ch[10];
#define N 131073
struct Tree
{
	int l,r,val,tag,rev;
}tr[N<<2];
int x,y,st,la,flag;

int read()
{
    int x=0,f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='(')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	if(ch==')')f=1;
    return x*2-f;
}

void Build(int p,int l,int r)
{
	tr[p].l = l, tr[p].r = r, tr[p].tag = -1;
	if (l == r) return;
	int mid = (l+r) >> 1;
	Build(p<<1,l,mid); Build(p<<1|1,mid+1,r);
}
void push_down(int p)
{
	int tag = tr[p].tag, rev = tr[p].rev;
	tr[p].tag = -1, tr[p].rev = 0;
	if (tr[p].l == tr[p].r)
	{
		if (tag != -1) tr[p].val = tag;
		tr[p].val ^= rev;
		return;
	}
	if (tag != -1)
	{
		tr[p<<1].tag = tr[p<<1|1].tag = tag;
		tr[p<<1].rev = tr[p<<1|1].rev = 0;
	}
	tr[p<<1].rev ^= rev, tr[p<<1|1].rev ^= rev;
}

int Query(int p,int xx)
{
	push_down(p);
	int l = tr[p].l, r = tr[p].r, mid = (l+r) >> 1;
	if (l == r) return tr[p].val;
	if (xx<=mid) return Query(p<<1,xx); else return Query(p<<1|1,xx);
}
void Modify(int p,int L,int R,int v)
{
	if (R<L) return;
	push_down(p);
	int l = tr[p].l, r = tr[p].r, mid = (l+r) >> 1;
	if (l == L && R == r)
	{
		if (v == -1) tr[p].rev ^= 1; else tr[p].tag = v;
		return;
	}
	if (R <= mid) Modify(p<<1,L,R,v);
	else if (L > mid) Modify(p<<1|1,L,R,v);
	else Modify(p<<1,L,mid,v), Modify(p<<1|1,mid+1,R,v);
}

void Rev(int p,int L,int R) { Modify(p,L,R,-1);}

int main()
{
	Build(1,1,N);
	while (scanf("%s",ch) != EOF)
	{
		x = read(), y = read();
		x += 2; y += 2;
		switch (ch[0])
		{
			case 'U': Modify(1,x,y,1); break;
			case 'I': Modify(1,1,x-1,0); Modify(1,y+1,N,0); break;
			case 'D': Modify(1,x,y,0); break;
			case 'C': Modify(1,1,x-1,0); Modify(1,y+1,N,0); Rev(1,x,y); break;
			case 'S': Rev(1,x,y); break;
		}
	}
	st = la = -1; flag = 0;
	for (int i=1;i<=N;++i)
	if (Query(1,i))
	{
		if (st == -1) st = i;
		la = i;
	}
	else
	{
		if (st != -1)
		{
			if (flag) printf(" ");	else flag = 1;
			if (st & 1) printf("("); else printf("[");
			printf("%d,%d",st/2-1,(la+1)/2-1);
			if (la & 1) printf(")"); else printf("]");
		}
		la = st = -1;
	}
	if (!flag) puts("empty set");
	return 0;
}

4364: [IOI2014]wall砖墙

线段树乱搞..乱更新一下QAQ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define NN 2000010
int n,m,op,l,r,x,mx1[NN<<2],mx2[NN<<2];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline void push_down(int p)
{
	int l = p<<1, r = p<<1|1;
	if (mx2[p] > mx1[l]) mx1[l] = mx2[l] = mx2[p]; else if (mx2[p] > mx2[l]) mx2[l] = mx2[p];
	if (mx2[p] > mx1[r]) mx1[r] = mx2[r] = mx2[p]; else if (mx2[p] > mx2[r]) mx2[r] = mx2[p];
	if (mx1[p] < mx2[l]) mx1[l] = mx2[l] = mx1[p]; else if (mx1[p] < mx1[l]) mx1[l] = mx1[p];
	if (mx1[p] < mx2[r]) mx1[r] = mx2[r] = mx1[p]; else if (mx1[p] < mx1[r]) mx1[r] = mx1[p];
}

inline void push_up(int p)
{
	mx1[p] = max(mx1[p<<1],mx1[p<<1|1]);
	mx2[p] = min(mx2[p<<1],mx2[p<<1|1]); 
}

inline void Update1(int L,int R,int l,int r,int p,int xx)
{
	if (L == l && R == r) { mx1[p] = max(mx1[p],xx), mx2[p] = max(mx2[p],xx); return;}
	int mid = (l+r) >> 1;
	push_down(p);
	if (R <= mid) Update1(L,R,l,mid,p<<1,xx);
	else if (L > mid) Update1(L,R,mid+1,r,p<<1|1,xx);
	else Update1(L,mid,l,mid,p<<1,xx), Update1(mid+1,R,mid+1,r,p<<1|1,xx);
	push_up(p);
}

inline void Update2(int L,int R,int l,int r,int p,int xx)
{
	if (L == l && R == r) { mx1[p] = min(mx1[p],xx), mx2[p] = min(mx2[p],xx); return;}
	int mid = (l+r) >> 1;
	push_down(p);
	if (R <= mid) Update2(L,R,l,mid,p<<1,xx);
	else if (L > mid) Update2(L,R,mid+1,r,p<<1|1,xx);
	else Update2(L,mid,l,mid,p<<1,xx), Update2(mid+1,R,mid+1,r,p<<1|1,xx);
	push_up(p);
}

inline void Build(int p,int l,int r)
{
	if (l == r)	{ printf("%d\n",mx1[p]); return; }
	int mid = (l+r) >> 1;
	push_down(p);
	Build(p<<1,l,mid), Build(p<<1|1,mid+1,r);
}

int main()
{
	n = read(), m = read();
	while (m--)
	{
		op = read();
		if (op == 1)
		{
			l = read(), r = read(), x = read();
			++l ,++r;
			Update1(l,r,1,n,1,x);
		}
		else
		{
			l = read(), r = read(), x = read();
			++l ,++r;
			Update2(l,r,1,n,1,x);
		}
	}
	Build(1,1,n);
	return 0;
}

3685: 普通van Emde Boas树

听说某Treap会被卡（反正不会写

糊里糊涂学习了一下zkw线段树的技巧 并没有完全弄会哎

在题解的帮助下终于写好了

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
using namespace std;

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,x,M = 0,cnt = 0,op;
bool tr[1<<21|1];

inline void Update(int xx,int d)
{
	if (!(d ^ tr[xx+M])) return;
	cnt += d ? 1 : -1;
	for (tr[xx+=M] = d, xx >>= 1;xx;xx >>= 1) tr[xx] = tr[xx<<1] | tr[xx<<1|1];
}
inline int Get_min(int xx)
{
	if (!cnt) return 0;
	for (;xx <= M;xx = tr[xx<<1] ? (xx<<1) : (xx<<1|1));
	return xx - M;
}
inline int Get_max(int xx)
{
	if (!cnt) return 0;
	for (;xx <= M;xx = tr[xx<<1|1] ? (xx<<1|1) : (xx<<1));
	return xx - M;
}
inline int Pre(int xx)
{
	if (!cnt) return 0;
	for (xx += M;xx != 1;xx >>= 1)
	if (xx & 1 && tr[xx^1])
	{
		xx ^= 1; break;
	}
	if (xx == 1) return 0;
	return Get_max(xx);
}
inline int Nxt(int xx)
{
	if (!cnt) return 0;
	for (xx += M;xx != 1;xx >>= 1)
	if (!(xx & 1) && tr[xx^1])
	{
		xx ^= 1; break;
	}
	if (xx == 1) return 0;
	return Get_min(xx);
}
inline void Judge(int xx)
{
	printf(tr[xx+M] ? "1\n" : "-1\n");
}

int main()
{
	n = read(), m = read();
	while ((1<<M) < n) M++;
	M = (1<<M) - 1;
	for (int i=1;i<=m;++i)
	{
		op = read();
		switch (op)
		{
			case 1: x = read() + 1; Update(x,1); break;
			case 2: x = read() + 1; Update(x,0); break;
			case 3: printf("%d\n",Get_min(1)-1); break;
			case 4: printf("%d\n",Get_max(1)-1); break;
			case 5: x = read() + 1; printf("%d\n",Pre(x) - 1); break;
			case 6: x = read() + 1; printf("%d\n",Nxt(x) - 1); break;
			case 7: x = read() + 1; Judge(x); break;
		}
	}
	return 0;
}

3813: 奇数国

感觉乱七八糟的东西捏在一起就会好烦啊呜呜呜

并不喜欢想怎么弄标记，然而不想怎么弄标记就做不出题呜呜呜

用两棵线段树，一棵维护乘积，一棵维护质因数（类似于状压压起来

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

#define N 305
#define mod 19961993
#define LL long long

LL bin[65],ni[N];
int n,pri[N]={0};
bool mark[N]={0};
struct Tree
{
	int l,r;
	LL v;
}tr[2][400010];

void Cal(int f,int k,int val)
{
	if (f == 0) tr[f][k].v = val;
	else
	{
		tr[f][k].v = 0;
		for (int i=1;i<=60;++i)
			if (val % pri[i] == 0) tr[f][k].v += bin[i-1];
	}
}

void update(int f,int p)
{
	if (f == 0) tr[f][p].v = tr[f][p<<1].v * tr[f][p<<1|1].v % mod;
	else tr[f][p].v = tr[f][p<<1].v | tr[f][p<<1|1].v;
}

void Build(int f,int p,int l,int r)
{
	tr[f][p].l = l, tr[f][p].r = r;
	int mid = (l+r) >> 1;
	if (l == r)
	{
		Cal(f,p,3); return;
	}
	Build(f,p<<1,l,mid), Build(f,p<<1|1,mid+1,r);
	update(f,p);
}

void Pre()
{
	ni[1] = 1;
	for (int i=2;i<=300;++i)
	{
		ni[i] = -mod/i * ni[mod%i] % mod;
		if (!mark[i]) pri[++pri[0]] = i;
		for (int j=1;j<=pri[0] && i*pri[j]<=300;++j)
		{
			mark[i*pri[j]] = 1;
			if (i%pri[j] == 0) break;
		}
	}
	bin[0] = 1;
	for (int i=1;i<=60;++i) bin[i] = bin[i-1] << 1;
	Build(0,1,1,100000); Build(1,1,1,100000);
}

LL que(int f,int p,int x,int y)
{
	int l = tr[f][p].l, r = tr[f][p].r, mid = (l+r) >> 1;
	if (l == x && r == y) return tr[f][p].v;
	if (y<=mid) return que(f,p<<1,x,y);
	else if (x > mid) return que(f,p<<1|1,x,y);
	else
	{
		if (f == 0) return que(f,p<<1,x,mid) * que(f,p<<1|1,mid+1,y) % mod;
		else return que(f,p<<1,x,mid) | que(f,p<<1|1,mid+1,y);
	}
}

int Query(int xx,int yy)
{
	LL tmp1 = que(0,1,xx,yy), tmp2 = que(1,1,xx,yy);
	for (int i=1;i<=60;++i)
		if (tmp2 & bin[i-1]) tmp1 = tmp1*(pri[i]-1) % mod * ni[pri[i]] %mod;
	tmp1 = (tmp1 + mod) % mod;
	return tmp1;
}

void Change(int f,int p,int xx,int val)
{
	int l = tr[f][p].l ,r = tr[f][p].r, mid = (l+r) >>1;
	if (l == r)
	{
		Cal(f,p,val); return;
	}
	if (xx<=mid) Change(f,p<<1,xx,val);
	else Change(f,p<<1|1,xx,val);
	update(f,p);
}
int main()
{
	Pre();
	n = read();
	for (int i=1;i<=n;++i)
	{
		int op = read(), x = read(), y = read();
		if (op == 0) printf("%d\n",Query(x,y));
		else Change(0,1,x,y), Change(1,1,x,y);
	}
	return 0;
}

2962: 序列操作

调得崩溃啊

最后错在把 p<<1|1 打成了p<<1 要死

用f[i]表示选i个数所有方案和，rt.f[i]=∑ⁱ_j=0 ls.f[j] ∗ rs.f[i−j]

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define NN 60050
#define mod 19940417
#define LL long long
int a[NN],b[25],c[NN][25],add[NN<<2],rev[NN<<2];
int n,q,x,y,z;
char ch[10];
struct Tree
{
	int f[25];
}tr[NN<<2];
int read() 
{
	bool f; char ch; int x;
	for (f=0,ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
	for (x=0;ch>='0';ch=getchar()) x=x*10+ch-'0'; if (f) x=-x; 
	return x;
}
void Update(int &xx,int yy)
{
	xx += yy;
	if (xx >= mod) xx -= mod;
	if (xx < 0) xx += mod;
}

void Cal(int p,int l,int r,int xx)
{
	for (int i=1;i<=20;++i)
	{
		int tmp =0, tx = 1;
		for (int j=i;j>=0;--j)
		{
			Update(tmp,(LL)tr[p].f[j] * c[r-l+1-j][i-j] % mod * tx %mod);
			tx = (LL) tx * xx % mod;
		}
		b[i] = tmp;
	}
	for (int i=1;i<=20;++i) tr[p].f[i] = b[i];
}
void push_down(int p,int l,int r)
{
	if (rev[p])
	{
		rev[p<<1] ^= 1, rev[p<<1|1] ^= 1;
		for (int i=1;i<=20;i+=2) tr[p<<1].f[i] = (mod - tr[p<<1].f[i]) % mod;
		for (int i=1;i<=20;i+=2) tr[p<<1|1].f[i] = (mod - tr[p<<1|1].f[i]) % mod;
		add[p<<1] = (mod - add[p<<1]) % mod, add[p<<1|1] = (mod - add[p<<1|1]) % mod;
		rev[p] = 0;
	}
	if (add[p])
	{
		int mid = (l+r) >> 1;
		Update(add[p<<1],add[p]), Update(add[p<<1|1],add[p]);
		Cal(p<<1,l,mid,add[p]), Cal(p<<1|1,mid+1,r,add[p]);
		add[p] = 0;
	}
}
void push_up(int p)
{
	for (int i=1;i<=20;++i) tr[p].f[i] = 0;
	for (int i=0;i<=20;++i)
		for (int j=0;i+j <= 20;++j)
		{
			if (i+j == 0) continue;
			Update(tr[p].f[i+j],(LL)tr[p<<1].f[i] * tr[p<<1|1].f[j] % mod);
		}
}
void Build(int p,int l,int r)
{
	tr[p].f[0] = 1;
	if (l == r)	{ tr[p].f[1] = a[l]; return; }
	int mid = (l+r) >> 1;
	Build(p<<1,l,mid), Build(p<<1|1,mid+1,r);
	push_up(p);
}

void Inc(int p,int l,int r,int L,int R,int x)
{
	if (L <= l && R >= r) {	Update(add[p],x); Cal(p,l,r,x); return;	}
	int mid = (l+r) >> 1;
	push_down(p,l,r);
	if (L <= mid) Inc(p<<1,l,mid,L,R,x);
	if (R > mid) Inc(p<<1|1,mid+1,r,L,R,x);
	push_up(p);
}
void Rev(int p,int l,int r,int L,int R)
{
	if (L <= l && R >= r)
	{
		rev[p] ^= 1;
		add[p] = (mod - add[p]) % mod;
		for (int i=1;i<=20;i+=2) tr[p].f[i] = (mod - tr[p].f[i]) % mod;
		return;
	}
	int mid = (l+r) >> 1;
	push_down(p,l,r);
	if (L <= mid) Rev(p<<1,l,mid,L,R);
	if (R > mid) Rev(p<<1|1,mid+1,r,L,R);
	push_up(p);
}

Tree Ask(int p,int l,int r,int L,int R)
{
	if (L <= l && R >= r) return tr[p];
	push_down(p,l,r);
	int mid = (l+r) >>1;
	Tree t,t1,t2;
	if (L > mid) t = Ask(p<<1|1,mid+1,r,L,R);
	else if (R <= mid) t = Ask(p<<1,l,mid,L,R);
	else
	{
		t.f[0] = 1;
		for (int i=1;i<=20;++i) t.f[i] = 0;
		t1 = Ask(p<<1,l,mid,L,mid), t2 = Ask(p<<1|1,mid+1,r,mid+1,R);
		for (int i=0;i<=20;++i)
			for (int j=0;j+i <= 20;++j)
			{
				if (i+j == 0) continue;
				Update(t.f[i+j],(LL)t1.f[i] * t2.f[j] % mod);
			}
	}
	return t;
}  

int main()
{
	n = read(), q = read();
	for (int i=0;i<=n;++i)
	{
		c[i][0] = c[i][i] = 1;
		for (int j=1;j<i;++j) c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
	}
	for (int i=1;i<=n;++i) a[i] = read(), a[i] = (a[i] % mod + mod) %mod;
	Build(1,1,n);
	while (q--)
	{
		scanf("%s",ch);
		if (ch[0] == 'I')
		{
			x = read(), y =read(), z = read();
			z = (z%mod+mod)%mod;
			Inc(1,1,n,x,y,z);
		}
		else if (ch[0] == 'R')
		{
			x = read(), y = read();
			Rev(1,1,n,x,y);
		}
		else
		{
			x = read(), y = read(), z = read();
			z = (z%mod+mod)%mod;
			Tree tmp = Ask(1,1,n,x,y);
			printf("%d\n",tmp.f[z] % mod);
		}
	}
	return 0;
}

1067: [SCOI2007]降雨量

错误有危险，分类需谨慎

分类讨论都有毒，剧毒

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#define lk k<<1
#define rk k<<1|1
using namespace std;
int n,m;
struct TREE
{
    int ly,ry,mx,f;
}tr[200001];
void read(int &xx)
{
    bool f=0; char CH;
    for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
    for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
}
void Build(int k,int l,int r)
{
    if (l==r) { read(tr[k].ly), read(tr[k].mx); tr[k].ry=tr[k].ly; tr[k].f=1; return; }
    int mid=(l+r)>>1;
    Build(lk,l,mid), Build(rk,mid+1,r);
    tr[k].f=(tr[lk].f && tr[rk].f);
    if (tr[lk].ry+1!=tr[rk].ly) tr[k].f=0;
    tr[k].ly=tr[lk].ly, tr[k].ry=tr[rk].ry, tr[k].mx=max(tr[lk].mx,tr[rk].mx);
}
int Get(int k,int xx)
{
    if (tr[k].ly==tr[k].ry)
    {
        if (tr[k].ly!=xx) return 0; else return tr[k].mx;
    }
    if (xx<=tr[lk].ry) return Get(lk,xx);
    else if (xx>=tr[rk].ly) return Get(rk,xx);
    return 0;
}
int Getne(int k,int xx)
{
    int l=tr[k].ly, r=tr[k].ry;
    if (l==r) return tr[k].ly;
    if (xx<tr[lk].ry) return Getne(lk,xx);
    else return Getne(rk,xx);
}
int Getla(int k,int xx)
{
    int l=tr[k].ly, r=tr[k].ry;
    if (l==r) return tr[k].ly;
    if (xx>tr[rk].ly) return Getla(rk,xx);
    else return Getla(lk,xx);
}
int Ask(int k,int xx,int yy,int num)
{
    bool flag=0;
    if (xx<tr[k].ly) flag=1, xx=tr[k].ly;
    if (tr[k].ly==xx & tr[k].ry==yy)
    { if (tr[k].mx>=num) return 0; else if (tr[k].f&& !flag) return 1; else return 2;    }
    if (yy<=tr[lk].ry) { return Ask(lk,xx,yy,num);}
    else if (xx>=tr[rk].ly) { return Ask(rk,xx,yy,num);}
    else
    {
        int ta=Ask(lk,xx,tr[lk].ry,num);
        int tb=Ask(rk,tr[rk].ly,yy,num);
        if (!ta || !tb) return 0;
        else if (tr[lk].ry+1 != tr[rk].ly) return 2; else return 1;
    }
}
int main()
{
    read(n);
    Build(1,1,n);
    read(m);
    int ll,rr;
    for (int i=1;i<=m;++i)
    {
        read(ll), read(rr);
        if (rr<ll) { puts("false"); continue;}
        int lnum=Get(1,ll), rnum=Get(1,rr);
        if (!lnum && !rnum) {   puts("maybe"); continue; }
        else
        {
            int st=Getne(1,ll), en=Getla(1,rr);
            if (!lnum)
            {
                if (st>en || rr==en) { puts("maybe"); continue;  }
                int flag=Ask(1,st,en,rnum);
                if (!flag) puts("false"); else puts("maybe"); continue;
            }
            else if (!rnum)
            {
                if (st>en || ll==st) { puts("maybe"); continue; }
                int flag=Ask(1,st,en,lnum);
                if (!flag) puts("false"); else puts("maybe"); continue;
            }
            else
            {
                if (rnum>lnum) { puts("false"); continue;}
                if (st>en) {if (ll+1==rr) puts("true"); else puts("maybe"); continue;}
                int flag=Ask(1,st,en,rnum);
                if (!flag) puts("false");
                else if (flag==1)
                {
                    if (ll+1==st && rr-1==en) puts("true"); else puts("maybe");
                }
                else if (flag==2) puts("maybe");
                else puts("false");
            }
        }
    }
    return 0;
}

4373: 算术天才⑨与等差数列

在观摩了各种gcd做法后选择死亡

然后意外发现了一片净土

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define lk k<<1
#define rk k<<1|1
const LL mod = 1000000009, SIX = 833333341; //SIX为6的逆元
const int NN = 300005,INF = 0x3f3f3f3f;
struct TR
{
	LL s1,s2,mn;
}tr[NN<<2];
int n,m,op,x,y,z,cnt=0;
LL a[NN];
bool flag;
LL ksm(LL xx,LL yy) 
{
	LL sum=1ll;
	for (xx%=mod;yy;xx=xx*xx%mod,yy>>=1) if (yy&1) sum=sum*xx%mod;
	return sum;
}
void push_up(int k)
{
	tr[k].s1 = tr[lk].s1 + tr[rk].s1;
	tr[k].s2 = (tr[lk].s2 + tr[rk].s2) % mod;
	tr[k].mn = min(tr[lk].mn,tr[rk].mn);
}

void Build(int k,int l,int r)
{
	if (l == r)
	{
		tr[k].s1 = tr[k].mn = a[l];
		tr[k].s2 = a[l] * a[l] % mod;
		return;
	}
	int mid = (l+r) >> 1;
	Build(lk,l,mid), Build(rk,mid+1,r);
	push_up(k);
}
void Change(int k,int l,int r,int p,LL v)
{
	if (l == r)
	{
		tr[k].s1 = tr[k].mn = v;
		tr[k].s2 = v*v % mod;
		return;
	}
	int mid = (l+r) >> 1;
	if (p <= mid) Change(lk,l,mid,p,v); else Change(rk,mid+1,r,p,v);
	push_up(k);
}

LL Query(int k,int l,int r,int L,int R,int t)
{
	if (L<=l && R>=r)
	{
		if (t == 1) return tr[k].s1; else return tr[k].s2;
	}
	int mid = (l+r) >> 1;
	LL pre = 0ll;
	if (L <= mid) pre += Query(lk,l,mid,L,R,t);
	if (R > mid) pre += Query(rk,mid+1,r,L,R,t);
	if (t == 2) pre %= mod;
	return pre;
}

LL Query_min(int k,int l,int r,int L,int R)
{
	if (L<=l && R>=r) return tr[k].mn;
	int mid = (l+r) >> 1;
	LL pre = INF;
	if (L <= mid) pre = min(pre,Query_min(lk,l,mid,L,R));
	if (R > mid) pre = min(pre,Query_min(rk,mid+1,r,L,R));
	return pre;
}

LL Get1(LL x,LL l,LL k)
{
	return x * l + (l - 1) * l / 2 * k;
}
LL Get2(LL x,LL l,LL k)
{
	LL ret = x * x % mod * l % mod;
	ret = (ret + (l - 1) * l % mod * k % mod * x % mod) % mod;
	ret += l * (l - 1) % mod * (2 * l - 1) % mod * k % mod * k % mod * SIX % mod;
	return ret % mod;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%lld",&a[i]);
	Build(1,1,n);
	while (m--)
	{
		scanf("%d",&op);
		if (op == 1) scanf("%d%d",&x,&y), x ^= cnt, y ^= cnt, Change(1,1,n,x,y);
		else
		{
			scanf("%d%d%d",&x,&y,&z), x ^= cnt, y ^= cnt, z ^= cnt;
			flag = 1;
			LL minn = Query_min(1,1,n,x,y);
			LL sum = Get1(minn,y-x+1,z);
			if (sum != Query(1,1,n,x,y,1)) flag = 0;
			if (flag && Get2(minn,y-x+1,z) != Query(1,1,n,x,y,2)) flag = 0;
			if (flag) puts("Yes"), ++cnt; else puts("No");
		}
	}
	return 0;
}

1858: [Scoi2010]序列操作

维护各种操作，强行上线段树即可。

部分说明如下：

$l0/l1$维护该区段从左边开始最长的连续$0/1$

对这些值进行维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read()
{
	int x=0; bool f=0; char ch;
	for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
	for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; if (f) x=-x;
	return x;
}
const int NN = 100005;
int n,m;
struct TR
{
	int l,r,l0,r0,l1,r1,mx0,mx1,sum0,sum1,num,rev,c;
}tr[NN<<2];

void Rev(int k)
{
	swap(tr[k].l0,tr[k].l1), swap(tr[k].r0,tr[k].r1), swap(tr[k].mx0,tr[k].mx1), swap(tr[k].sum0,tr[k].sum1);
	if (tr[k].num != -1) tr[k].num ^= 1;
}
void Color(int k,int v)
{
	tr[k].rev = 0;
	int sum = tr[k].r - tr[k].l + 1;
	if (v == 0)
	{
		tr[k].sum0 = tr[k].l0 = tr[k].r0 = tr[k].mx0 = sum;
		tr[k].sum1 = tr[k].l1 = tr[k].r1 = tr[k].mx1 = 0;
	}
	else
	{
		tr[k].sum0 = tr[k].l0 = tr[k].r0 = tr[k].mx0 = 0;
		tr[k].sum1 = tr[k].l1 = tr[k].r1 = tr[k].mx1 = sum;
	}
	tr[k].num = v;
}
TR Merge(TR x,TR y)
{
	TR tmp;
	tmp.l = x.l, tmp.r = y.r;
	tmp.rev = 0, tmp.c = -1;
	tmp.l0 = x.l0, tmp.l1 = x.l1, tmp.r0 = y.r0, tmp.r1 = y.r1;
	tmp.mx0 = max(x.mx0,y.mx0), tmp.mx1 = max(x.mx1,y.mx1);
	tmp.mx0 = max(tmp.mx0,x.r0+y.l0), tmp.mx1 = max(tmp.mx1,x.r1+y.l1);
	tmp.sum0 = x.sum0 + y.sum0, tmp.sum1 = x.sum1 + y.sum1;
	if (x.num == 0) tmp.l0 = x.mx0 + y.l0;
		else if (x.num == 1) tmp.l1 = x.mx1 + y.l1;
	if (y.num == 0) tmp.r0 = y.mx0 + x.r0;
		else if (y.num == 1) tmp.r1 = y.mx1 + x.r1;
	if (x.num == y.num) tmp.num = x.num;
		else tmp.num = -1;
	return tmp;
}
void push_up(int k) { tr[k] = Merge(tr[k<<1],tr[k<<1|1]); }
void push_down(int k)
{
	if (tr[k].l == tr[k].r) return;
	if (tr[k].c != -1)
	{
		tr[k<<1].c = tr[k<<1|1].c = tr[k].c;
		Color(k<<1,tr[k].c), Color(k<<1|1,tr[k].c), tr[k].c = -1;
	}
	if (tr[k].rev)
	{
		tr[k<<1].rev ^= 1, tr[k<<1|1].rev ^= 1;
		Rev(k<<1), Rev(k<<1|1), tr[k].rev = 0;
	}
}
void Build(int k,int l,int r)
{
	tr[k].l = l, tr[k].r = r, tr[k].c = -1;
	if (l == r)
	{
		tr[k].num = read();
		if (tr[k].num) tr[k].l1 = tr[k].r1 = tr[k].mx1 = tr[k].sum1 = 1;
		else tr[k].l0 = tr[k].r0 = tr[k].mx0 = tr[k].sum0 = 1;
		return;
	}
	int mid = (l+r) >> 1;
	Build(k<<1,l,mid), Build(k<<1|1,mid+1,r);
	push_up(k);
}
void Change(int k,int x,int y,int v)
{
	push_down(k);
	int l=tr[k].l, r=tr[k].r;
	if (l == x && r == y) { Color(k,v), tr[k].c = v; return; }
	int mid = (l+r) >> 1;
	if (y <= mid) Change(k<<1,x,y,v);
	else if (x > mid) Change(k<<1|1,x,y,v);
	else Change(k<<1,x,mid,v), Change(k<<1|1,mid+1,y,v);
	push_up(k);
}
void Rever(int k,int x,int y)
{
	push_down(k);
	int l = tr[k].l, r = tr[k].r;
	if (l == x && r == y) { Rev(k), tr[k].rev = 1; return; }
	int mid = (l+r) >> 1;
	if (y <= mid) Rever(k<<1,x,y);
	else if (x > mid) Rever(k<<1|1,x,y);
	else Rever(k<<1,x,mid), Rever(k<<1|1,mid+1,y);
	push_up(k);
}
TR Query(int k,int x,int y)
{
	push_down(k);
	int l = tr[k].l, r = tr[k].r;
	if (l == x && r == y) return tr[k];
	int mid = (l+r) >> 1;
	if (y <= mid) return Query(k<<1,x,y);
	else if (x > mid) return Query(k<<1|1,x,y);
	else return Merge(Query(k<<1,x,mid),Query(k<<1|1,mid+1,y));
}
int Q_sum(int k,int x,int y)
{
	push_down(k);
	int l = tr[k].l, r = tr[k].r;
	if (l == x && y == r) return tr[k].sum1;
	int mid = (l+r) >> 1;
	if (y <= mid) return Q_sum(k<<1,x,y);
	else if (x > mid) return Q_sum(k<<1|1,x,y);
	else return Q_sum(k<<1,x,mid)+Q_sum(k<<1|1,mid+1,y);
}
int main()
{
	n = read(), m = read();
	Build(1,1,n);
	int x,y,op;
	for (int i=1;i<=m;++i)
	{
		op = read(), x = read()+1, y = read()+1;
		switch (op)
		{
			case 0: Change(1,x,y,0); break;
			case 1: Change(1,x,y,1); break;
			case 2: Rever(1,x,y); break;
			case 3: printf("%d\n",Q_sum(1,x,y)); break;
			case 4: printf("%d\n",Query(1,x,y).mx1); break;
		}
	}
	return 0;
}