orz PoPoQQQ 的神题。
我的想法是：给每一个高度都维护一个 $01$ 序列，大概就是维护一个 $Map[i][j]$ 的矩阵，然后 $Map[i][j]$ 表示第 $i$ 根柱子的高度是否 $\ge j$。
那么怎么维护 $Map[i][j]$ 呢。。？
首先我们把柱子按照高度从小到大排序，然后依次给每个高度建主席树，初始时 $Map[i][0]$ 全是 $1$，然后如果当前高度 $i$ 比某个柱子 $j$ 的高度要大了，那么就单点修改 $Map[i][j]$，然后这个就是主席树动态开节点的经典操作嘛。然后我们就相当于是要维护每一个高度的主席树，并记录其最长连续子段，记高度 $i$ 的主席树的最长连续子段长 $len_i$，那么最大子矩阵就是：
$$max\{i\times len_i | i = 1 - Max\_height\}$$
然后每次单点修改只会改变一个主席树的最长连续子段，所以我们可以再弄一个堆维护这个答案。
时间空间复杂度均为 $O((n+m)\log h + h)$，可以过掉本题。
其实 $h$ 可以扩大到 $10^9$，这样的话我们就需要离散化一下，反正有用的高度只有 $O(n + m)$ 种。
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 100000 + 5
#define M 1000000 + 5
#define SIZE 10000000 + 5 int n, m, Max, tot, A[N], Ord[N], Root[M]; struct Segment_Tree
{
int l, r, Lcombo, Rcombo, combo;
}h[SIZE]; struct Node
{
int id;
LL square;
Node (int _id = , LL _square = ) {id = _id, square = _square;}
bool operator < (const Node a) const
{
return square < a.square || (square == a.square && id < a.id);
}
}; priority_queue <Node> Q; inline LL getint()
{
char ch = '\n';
for (; ch != '-' && (ch > '' || ch < ''); ch = getchar()) ;
int f = ch == '-' ? - : ;
LL res = ch == '-' ? : ch - '';
for (ch = getchar(); ch >= '' && ch <= ''; ch = getchar())
res = (res << ) + (res << ) + ch - '';
return res * f;
} inline bool cmp(int u, int v)
{
return A[u] < A[v];
} inline void Build(int &x, int l, int r)
{
x = ++ tot;
h[x].Lcombo = h[x].Rcombo = h[x].combo = r - l + ;
if (l == r) return ;
int mid = l + r >> ;
Build(h[x].l, l, mid);
Build(h[x].r, mid + , r);
} inline void update(int x, int l, int r)
{
int mid = l + r >> ;
if (h[h[x].l].Lcombo == mid - l + )
h[x].Lcombo = h[h[x].l].Lcombo + h[h[x].r].Lcombo;
else h[x].Lcombo = h[h[x].l].Lcombo;
if (h[h[x].r].Rcombo == r - mid)
h[x].Rcombo = h[h[x].r].Rcombo + h[h[x].l].Rcombo;
else h[x].Rcombo = h[h[x].r].Rcombo;
h[x].combo = max(max(h[h[x].l].combo, h[h[x].r].combo), h[h[x].l].Rcombo + h[h[x].r].Lcombo);
} inline void Modify(int &x, int l, int r, int t)
{
h[++ tot] = h[x];
x = tot;
if (l == r)
{
h[x].Lcombo = h[x].Rcombo = h[x].combo = ;
return ;
}
int mid = l + r >> ;
if (t <= mid) Modify(h[x].l, l, mid, t);
else Modify(h[x].r, mid + , r, t);
update(x, l, r);
} int main()
{
n = getint(), m = getint();
for (int i = ; i <= n; Ord[i] = i, i ++)
{
A[i] = getint();
Max = max(Max, A[i]);
}
sort(Ord + , Ord + n + , cmp);
Build(Root[], , n);
for (int i = , t = ; i <= Max; i ++)
{
Root[i] = Root[i - ];
for (; A[Ord[t]] == i - && t <= n; t ++)
Modify(Root[i], , n, Ord[t]);
Q.push(Node(i, (LL) h[Root[i]].combo * i));
}
Node x = Q.top();
LL last = x.square;
printf("%lld\n", last);
while (m --)
{
int pos = (int) (getint() ^ last);
Modify(Root[A[pos]], , n, pos);
Q.push(Node(A[pos], (LL) h[Root[A[pos]]].combo * A[pos]));
A[pos] --;
Node x;
for (x = Q.top(); (LL) x.id * h[Root[x.id]].combo != x.square; Q.pop(), x = Q.top()) ;
last = x.square;
printf("%lld\n", last);
} return ;
}
Rectangle_Gromah