题意：初始序列 1, 2, ..., n，m次操作(1 <= n,m<= 50000)，每次操作可为：
D l r，将区间[l, r]中的所有数复制一次；
Q l r，输出区间[l, r]中同一数字个数的最大值。
(0 <= r – l <= 10^8, 1 <= l, r <= 序列元素个数)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4973
——>>因为区间内数字是依次递增的，所以可以以数字为叶建线段树去维护区间同一数字个数最大值。。
原查询区间[l, r]，转换成区间[l位对应的数字，r位对应的数字]的线段树查询。。
接着就是SB的线段树操作了。。
注意区间的分段处理。。
#include <cstdio>
#include <algorithm>#define lc (o << 1)
#define rc ((o << 1) | 1)using std::max;const int MAXN = 50000 + 10;int mul[MAXN << 2];
long long sum[MAXN << 2], maxv[MAXN << 2];int ReadInt()
{int ret = 0;char ch;while ((ch = getchar()) && ch >= '0' && ch <= '9'){ret = ret * 10 + ch - '0';}return ret;
}void Pushdown(int o)
{if (mul[o]){mul[lc] += mul[o];mul[rc] += mul[o];sum[lc] <<= mul[o];sum[rc] <<= mul[o];maxv[lc] <<= mul[o];maxv[rc] <<= mul[o];mul[o] = 0;}
}void Maintain(int o)
{sum[o] = sum[lc] + sum[rc];maxv[o] = max(maxv[lc], maxv[rc]);
}void Build(int o, int L, int R)
{mul[o] = 0;if (L == R){sum[o] = 1;maxv[o] = 1;return;}int M = (L + R) >> 1;Build(lc, L, M);Build(rc, M + 1, R);Maintain(o);
}int QueryFigure(int o, int L, int R, long long index)
{if (L == R) return L;Pushdown(o);int M = (L + R) >> 1;return index <= sum[lc] ? QueryFigure(lc, L, M, index) : QueryFigure(rc, M + 1, R, index - sum[lc]);
}long long QuerySum(int o, int L, int R, int ql, int qr)
{if (ql <= L && R <= qr) return sum[o];Pushdown(o);int M = (L + R) >> 1;long long ret = 0;if (ql <= M){ret += QuerySum(lc, L, M, ql, qr);}if (qr > M){ret += QuerySum(rc, M + 1, R, ql, qr);}return ret;
}void UpdateInterval(int o, int L, int R, int ql, int qr)
{if (ql <= L && R <= qr){sum[o] <<= 1;maxv[o] <<= 1;mul[o]++;return;}Pushdown(o);int M = (L + R) >> 1;if (ql <= M){UpdateInterval(lc, L, M, ql, qr);}if (qr > M){UpdateInterval(rc, M + 1, R, ql, qr);}Maintain(o);
}void UpdateLeaf(int o, int L, int R, int q, int add)
{if (L == R){sum[o] += add;maxv[o] += add;return;}Pushdown(o);int M = (L + R) >> 1;if (q <= M){UpdateLeaf(lc, L, M, q, add);}else{UpdateLeaf(rc, M + 1, R, q, add);}Maintain(o);
}void Update(int n, int l, int r, int ql, int qr)
{if (ql == qr){UpdateLeaf(1, 1, n, ql, r - l + 1);}else{int addLeft = QuerySum(1, 1, n, 1, ql) - l + 1;int addRight = r - QuerySum(1, 1, n, 1, qr - 1);UpdateLeaf(1, 1, n, ql, addLeft);UpdateLeaf(1, 1, n, qr, addRight);if (qr - ql >= 2){UpdateInterval(1, 1, n, ql + 1, qr - 1);}}
}long long QueryMax(int o, int L, int R, int ql, int qr)
{if (ql <= L && R <= qr) return maxv[o];Pushdown(o);int M = (L + R) >> 1;long long ret = 0;if (ql <= M){ret = max(ret, QueryMax(lc, L, M, ql, qr));}if (qr > M){ret = max(ret, QueryMax(rc, M + 1, R, ql, qr));}return ret;
}long long Query(int n, int l, int r, int ql, int qr)
{long long ret = 0;if (ql == qr){ret = r - l + 1;}else{ret = max(ret, QuerySum(1, 1, n, 1, ql) - l + 1);ret = max(ret, r - QuerySum(1, 1, n, 1, qr - 1));if (qr - ql >= 2){ret = max(ret, QueryMax(1, 1, n, ql + 1, qr - 1));}}return ret;
}int main()
{int t, n, m, l, r, ql, qr, kase = 0;char op;scanf("%d", &t);getchar();while (t--){scanf("%d%d", &n, &m);getchar();Build(1, 1, n);printf("Case #%d:\n", ++kase);while (m--){op = getchar(); getchar();l = ReadInt();r = ReadInt();ql = QueryFigure(1, 1, n, l);qr = QueryFigure(1, 1, n, r);if (op == 'D'){Update(n, l, r, ql, qr);}else{printf("%I64d\n", Query(n, l, r, ql, qr));}}}return 0;
}