题意：有一群小朋友围成一个环，编号1,2,3…N。每个人手上握着一个非0的数字，首先第K个人出列，然后看他手上的数字，假设为m，则从下一个开始第m个人出列，一直如此。并设i为小于等于N的最大反素数，问第i个出列的人得编号，i的约数个数。（设g（i）为i的约数的个数，若任意j<i，都有g（j）<g（i）则i为反素数）。
首先要得到[0，N]的最大反素数（怎么得到下面再说），然后模拟出列操作，用线段树来优化使得每次出列在O（logN）时间内完成。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; #define maxn 100005 int maxsub[maxn<<], minsub[maxn<<];
int lmax[maxn<<], rmax[maxn<<];
int lmin[maxn<<], rmin[maxn<<];
int sum[maxn<<]; void PushUp(int rt) {
int l = rt<<;
int r = l+;
sum[rt] = sum[l] + sum[r];
maxsub[rt] = max(max(maxsub[l], maxsub[r]), rmax[l]+lmax[r]);
minsub[rt] = min(min(minsub[l], minsub[r]), rmin[l]+lmin[r]);
lmax[rt] = max(lmax[l], sum[l]+lmax[r]);
rmax[rt] = max(rmax[r], sum[r]+rmax[l]);
lmin[rt] = min(lmin[l], sum[l]+lmin[r]);
rmin[rt] = min(rmin[r], sum[r]+rmin[l]);
} void build(int l, int r, int rt) {
if (l == r) {
scanf("%d", &sum[rt]);
minsub[rt] = lmax[rt] = rmax[rt] = lmin[rt] = rmin[rt] = maxsub[rt] = sum[rt];
return;
}
int m = (l+r)>>;
build(l, m, rt<<);
build(m+, r, rt<<|);
PushUp(rt);
} void update(int target, int val, int l, int r, int rt) {
if (l == r) {
sum[rt] = maxsub[rt] = minsub[rt] = val;
lmax[rt] = rmax[rt] = lmin[rt] = rmin[rt] = val;
return;
}
int m = (l+r)>>;
if (m >= target) update(target, val, l, m, rt<<);
else update(target, val, m+, r, rt<<|);
PushUp(rt);
} int main()
{
int n, m, ans; scanf ("%d", &n);
build(, n, );
scanf("%d", &m);
while (m--) {
int a, b;
scanf ("%d%d", &a, &b);
update(a, b, , n, );
if (sum[] == maxsub[]) //序列全为非负数的时候
ans = sum[] - minsub[];
else ans = max(maxsub[], sum[]-minsub[]);
printf ("%d\n", ans);
}
return ;
}