1. 要依次插入$n$个数，分别为$1,2, ..., n$，第$i$个数要插在当前第$a_i$个数的右边，求最后序列。

【题解】

很明显考虑从后往前插入，那么我们就能用一棵线段树搞定啦！

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <iostream>
# include <algorithm>

using namespace std;

int n, a[1000010], f[1000010];

// ================================ //
int lc[8000010], rc[8000010];
int w[8000010];
inline void build(int x, int l, int r) {
	lc[x]=l, rc[x]=r; 
	if(l==r) {
		w[x] = 1;
 		return;
	}
	int mid=l+r>>1;
	build(x<<1, l, mid);
	build(x<<1|1, mid+1, r);
	w[x] = w[x<<1] + w[x<<1|1];
}

inline int get(int x, int c) {
	int L=lc[x], R=rc[x];
	w[x] --;
	if(L == R) return L;
	if(w[x<<1] >= c) return get(x<<1, c);
	else return get(x<<1|1, c-w[x<<1]);
}
// ================================ //
int cx;char ch;
inline int getint() {
	cx=0;
	ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) {
		cx=(cx<<3)+(cx<<1)+ch-'0';
		ch=getchar();
	}
	return cx;
}
int wss[8], wsn=0;
inline void putint(int x) {
	wsn=0;
	while(x) {
		wss[++wsn] = x%10;
		x=x/10;
	}
	for (int i=wsn; i>=1; --i) putchar(wss[i]+'0');
	putchar(' ');
}

int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	n=getint();
	for (int i=1; i<=n; ++i) a[i] = getint();
	build(1, 1, n);
	for (int i=n; i>=1; --i) {
		int pos = get(1, a[i]+1);
//		printf("POS=%d\n", pos);
		f[pos] = i; 

	}
	
	for (int i=1; i<=n; ++i) putint(f[i]); 
	puts("");
	
	return 0;
}

2. 给$n$个物品，有重量和价值，要求在重量不超过$m$的情况下，最大化价值。

$n \leq 40, m \leq 10^{18}$

【题解】这不就是折半？然后建线段树变成区间查询啦！

复杂度$O(n 2^{n/2})$

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>

using namespace std;

int n;
long long m;
long long x[50], w[50];

struct pir {
	long long sum;
	long long ws;
} p[2000100];
int pn=0;

long long ans=0;

int lc[5000010], rc[5000010];
long long wc[5000010], xl[5000010], xr[5000010];

inline long long MAX(long long a, long long b) {
	return a>b?a:b;
}

// ======================== //
inline void build(int x, int l, int r) {
	lc[x] = l, rc[x] = r;
	if(l == r) {
		wc[x] = p[l].ws;
		xl[x] = xr[x] = p[l].sum;
		return ;
	}
	int mid=l+r>>1;
	build(x<<1, l, mid);
	build(x<<1|1, mid+1, r);
	wc[x] = MAX(wc[x<<1], wc[x<<1|1]);
	xl[x] = xl[x<<1], xr[x] = xr[x<<1|1];
}

inline long long query(int x, long long xs) {
//	printf("x=%d, xs=%I64d, xl=%I64d, xr=%I64d\n", x, xs, xl[x], xr[x]);
	int l=lc[x], r=rc[x];
	if(xl[x] > xs) return 0;
	if(xr[x] <= xs) return wc[x];
	if(xs < xr[x<<1]) return query(x<<1, xs);
	else return MAX(query(x<<1, xs), query(x<<1|1, xs));
}
// ======================== //


inline void dfs1(int step, long long sum, long long ws) {
	if(sum>m) return;
	if(step == n/2+1) {
		p[++pn].sum = sum, p[pn].ws = ws;
		return ;
	}
	dfs1(step+1, sum+x[step], ws+w[step]);
	dfs1(step+1, sum, ws);
}

inline bool cmp(pir a, pir b) {
	return a.sum < b.sum || (a.sum == b.sum && a.ws < b.ws);
}

inline void dfs2(int step, long long sum, long long ws) {
	if(sum>m) return ;
	if(step == n+1) {
		if(m-sum<0) return;
//		printf("%d %I64d %I64d\n", step, m-sum, ws);
		long long cur = ws + query(1, m-sum);
		if(cur>ans) ans=cur;
		return ;
	}
	dfs2(step+1, sum+x[step], ws+w[step]);
	dfs2(step+1, sum, ws);
}



int main() {
	freopen("pack.in", "r", stdin);
	freopen("pack.out", "w", stdout);
	scanf("%d%I64d", &n, &m);
	
//	printf("%I64d\n", (long long)sizeof(p)+sizeof(x)+sizeof(w)+sizeof(lc)+sizeof(rc)+sizeof(wc)+sizeof(xl)+sizeof(xr));
	
	for (int i=1; i<=n; ++i)
		scanf("%I64d%I64d", &x[i], &w[i]);
	
	dfs1(1, 0, 0);
	sort(p+1, p+pn+1, cmp);
	
//	for (int i=1; i<=pn; ++i) {
//		printf("sum=%I64d ws=%I64d\n", p[i].sum, p[i].ws);
//	}
	build(1, 1, pn);
//	for (int i=1; i<=pn*4; ++i)
//		printf("i=%d, lc=%d, rc=%d, xl=%I64d, xr=%I64d, wx=%I64d\n", i, lc[i], rc[i], xl[i], xr[i], wc[i]);
	
	
	dfs2(n/2+1, 0, 0);
	// sum + pi < m && max(qi+ws)
	printf("%I64d\n", ans);
	
	return 0;
}

3. 给你一个线段树，每个节点的左儿子区间为$[l, k]$，右儿子为$[k+1, r]$，对于每个点任意选取$k$。

对于询问一个区间$[l, r]$，会访问到所有的叶子节点。对于$m$个询问，求出最少访问多少个节点。

$ n \leq 5000, m \leq 100000$

【题解】

区间dp。$f[i,j]$表示区间$[i,j]$的最少访问次数。那么转移方程很好列。之后直接套上四边形不等式优化就行啦

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>

using namespace std;

int n, m;
int f[5050][5050];
int p[5050][5050];
int w[5050][5050];
int left[5050], right[5050];

int main() {
	freopen("segment.in", "r", stdin);
	freopen("segment.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for (int i=1, a, b; i<=m; ++i) {
		scanf("%d%d", &a, &b);
		left[a] ++;
		right[b] ++;
	}
	for (int i=n; i>=1; --i) left[i] += left[i+1];
	for (int i=1; i<=n; ++i) right[i] += right[i-1];
	for (int i=1; i<=n; ++i)
		for (int j=i; j<=n; ++j) {
			w[i][j] = m-left[j+1]-right[i-1];
			if(i==j) f[i][j]=w[i][j], p[i][i] = i;
		}
	for (int len=1; len<=n; ++len) 
		for (int i=1; i<=n-len+1; ++i) {
			int j = i+len;
			f[i][j] = 2000000000LL;
			for (int k=p[i][j-1]; k<=p[i+1][j]; ++k)
				if(f[i][k] + f[k+1][j] + w[i][j] < f[i][j]) {
					f[i][j] = f[i][k] + f[k+1][j] + w[i][j];
					p[i][j] = k;
				} 
		}
	printf("%d\n", f[1][n]);	
	return 0;
}
/*
6 6
1 4
2 6
3 4
3 5
2 3
5 6
*/