1. 给出数列n，把它分为若干段。有四个子任务

子任务1: 最小化$\sum_{i=1}^{m-1} |b_{i} - b_{i+1} |$ 其中$m$表示分段数，$b_{i}$表示每段最大值。 (20%)

子任务2: 求使得上式最小的分段方案数。只要有一个分段不同，就是不同的方案数。(30%)

子任务3: 最小化$\sum_{i=1}^{m-1} (b_{i} - b_{i+1})^{2}$，$m, b$同上。 (20%)

子任务4: 求使得上式最小的分段方案数。只要有一个分段不同，就是不同的方案数。(30%)

$n \leq 100000$

【题解】

子任务1: 找到最大值并记录，在第一个最大值前维护单调栈即可。

子任务2: 单调栈代表元素之间间隔如果是$len$，答案就是所有$len+1$的乘积（划分在任意位置/不划分）

子任务3: 很明显这就要求单调栈代表元素必须选到，在单调栈上统计即可。

子任务4: 如果没有重复的数那么统计和2类似，有重复的数，那么这段的答案为所有$len+1$的乘积$-1$。

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <iostream>
using namespace std;
int n, p;
int syx[666666];

inline long long pow(long long a, int b) {
	long long s=1;
	while(b) {
		if(b&1)s=s*a%p;
		a=a*a%p;
		b>>=1;
	}
	return s%p;
}

int main() {
	freopen("equation.in", "r", stdin);
	freopen("equation.out", "w", stdout);

	scanf("%d%d", &n, &p);
	
	if(n == 1) {
		printf("1 0\n");
		return 0;
	}
	
	
//	printf("???");
	memset(syx, 0, sizeof(syx));
	for (int i=0; i<p; ++i) {
//		printf("i=%d, t=%d\n", i, t);
		syx[(int)((pow((long long)i, n) + (long long)i*(p-1)%p)%p)]++;
	}
	int a = 0;
	
//	printf("???");
	for (int i=0; i<p; ++i) {
//		printf("%d\n", syx[i]);
		if(syx[i] == 0) {
			a = -i;
			break;
		}
	}
	
//	printf("%d %d\n", mm, a);
	
//	printf("???");
	
	a=(a+p)%p;
	printf("1 ");
	for (int i=1; i<=n-2; ++i) printf("0 ");
	printf("%d ", p-1);
	printf("%d\n", a);
	
	return 0;
}

2. 求使得$n$次同余方程无解的一组系数。 $n \leq 100, p \leq 100000$

【题解】

如果$a_n = 1, a_1 = p-1$，考虑$x=0$和$x=1$，他们答案相同，那就一定会空出一个空位，找到这个空位即可。

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <iostream>
using namespace std;
int n, p;
int syx[666666];

inline int pow(long long a, int b) {
	long long s=1;
	while(b) {
		if(b&1)s=s*a%p;
		a=a*a%p;
		b>>=1;
	}
	return (int)s%p;
}

int main() {
	freopen("equation.in", "r", stdin);
	freopen("equation.out", "w", stdout);

	scanf("%d%d", &n, &p);
	
	if(n == 1) {
		printf("1 0\n");
		return 0;
	}
	
	
//	printf("???");
	memset(syx, 0, sizeof(syx));
	for (int i=0; i<p; ++i) {
		int t=pow((long long)i, n);
		t = (int)(((long long)t + (long long)i*(p-1)%p)%p);
//		printf("i=%d, t=%d\n", i, t);
		syx[t]++;
	}
	int a = 0, mm = p+1;
	
//	printf("???");
	for (int i=0; i<p; ++i) {
		//printf("%d\n", syx[i]);
		if(syx[i] < mm) {
			mm = syx[i];
			a = -i;
		}
	}
	
//	printf("%d %d\n", mm, a);
	
//	printf("???");
	
	a=(a+p)%p;
	printf("1 ");
	for (int i=1; i<n-1; ++i) printf("0 ");
	printf("%d %d\n", p-1, a);
	
	return 0;
}

3. 一个数列，求其中区间或值小于m的区间个数。

$n \leq 100000, m \leq 2^{30}-1, a_{i} \leq 2^{30}-1$

【题解】尺取维护或即可，或者预处理st表，枚举左端点二分右端点$O(1)$查询。

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <iostream>
using namespace std;

int n, m;
int a[1000020][32];
int an=0;
long long ans = 0;
int cur[32];
int curr[32];
int pow2[32];

int x=0;char ch;
inline int getint() {
	x=0, ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) {
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}

inline bool can(int now) {
	for (int j=1; j<=31; ++j) curr[j]=cur[j];
	for (int j=1; j<=31; ++j) curr[j] = curr[j]+a[now][j];
	int ansx=0;
	for (int j=1; j<=31; ++j) ansx = ansx + (curr[j]>=1) * pow2[j];
	if(ansx<m) {
		for (int j=1; j<=31; ++j) cur[j] = curr[j];
		return 1;
	}
	return 0;
}


int main() {
	freopen("evolve.in", "r", stdin);
	freopen("evolve.out", "w", stdout);
	n = getint(); m = getint();
	pow2[1] = 1;
	for (int i=2; i<=31; ++i) pow2[i] = pow2[i-1] * 2;
	for (int i=1, t; i<=n; ++i) {
		t = getint();
		an=0;
		while(t) {
			a[i][++an] = t&1;
			t>>=1;
		}
		a[i][0] = an;
	}
	
	int beg, end = 0;
	
	for (beg=1; beg<=n; ++beg) {
		if(end < beg) {
			end = beg;
			for (int i=1; i<=31; ++i) cur[i] = a[beg][i];
		}
		while(can(end+1) && end+1 <= n) ++end;
		ans += end-beg;
//		int ansx=0;
//		for (int j=1; j<=30; ++j) ansx = ansx + (cur[j]>=1) * pow2[j];
//		cout<<"ansx="<<ansx<<endl;
//		printf("%d %d\n", beg, end);
		for (int j=1; j<=31; ++j) cur[j] -= a[beg][j];
	}
	
	printf("%I64d\n", ans);
	
	return 0;
}