#2461. 「2018 集训队互测 Day 1」完美的队列
传送门：
题解：
直接做可能一次操作加入队列同时会弹出很多数字，无法维护；一个操作的有效区间是连续的，考虑找到操作x结束的时间ed[x],即执行(x,ed[x]]可以将x加入的数全部弹出，这样用一个vis记录数字次数就可以维护个数；
一种比较暴力的做法是：枚举x，用一个线段树维护还可以放多少个元素，枚举ed[x]更新，但是这样不满足单调性无法two-pointers;
考虑分块。ed[x]即对x的每一个块的ed取max
考虑整块。枚举每一个整块，用一个b维护还可以放的元素初始化为ai，cov维护整块被完整覆盖了多少次，枚举x，再枚举ed[x]，当mx(bi)-cov==0时表示x的当前块在这里结束，更新ed[x]，此时是有单调性的可以two-pointers，复杂度$O(m \sqrt{n})$；
考虑散块。在处理完整块的时候枚举整块里的元素处理散块，如果直接像整块那样枚举m个操作，复杂度是$O(nm)$的，但如果在处理整块时用一个d数组记录下每一个和当前整块相交但不覆盖的操作，这样就是$O(m \sqrt{n})$的，因为一个操作最多有$\sqrt{n}$个散块，同样枚举d的元素做two-pointers，注意这是一个散块的ed不一定只出现在d里，可能出现在d[i]和d[i-1]中间某个将整块完整覆盖的操作，所以还需要记录完全覆盖整块的操作的前缀和s[], 覆盖整块的编号c[] ， d[i]前面的第一个覆盖整块的操作e[i]。
细节多；
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#define Run(i,l,r) for(int i=l;i<=r;i++)
#define Don(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=;
int n,m,a[N],b[N],c[N],d[N],e[N],vis[N],num,cn,dn,l[N],r[N],v[N],ed[N],s[N];
inline void upd(int&x,int y){if(x<y)x=y;}
struct node{int x,y;};
vector<node>g[N];
char gc(){
static char*p1,*p2,S[];
if(p1==p2)p2=(p1=S)+fread(S,,,stdin);
return(p1==p2)?EOF:*p1++;
}//
int rd(){
int x=; char C=gc();
while(C<''||C>'')C=gc();
while(C>=''&&C<='')x=(x<<)+(x<<)+C-'',C=gc();
return x;
}//
int main(){
//freopen("loj2461.in","r",stdin);
//freopen("loj2461.out","w",stdout);
n=rd(); m=rd();
Run(i,,n)a[i]=rd();
Run(i,,m)l[i]=rd(),r[i]=rd(),v[i]=rd();
int B = sqrt(n);
for(int L=;L<=n;L+=B){
cn=dn=;
int R=min(n,L+B-),mx=,cov=;
Run(i,L,R)upd(mx,b[i]=a[i]);
for(int i=,j=;i<=m;i++){
if(l[i]<=L&&r[i]>=R)cov--;
else if(l[i]<=R&&r[i]>=L){
Run(k,max(l[i],L),min(r[i],R))b[k]++;
mx=;Run(k,L,R)upd(mx,b[k]);
}
while(j<=m&&mx-cov>){
j++;
if(l[j]<=L&&r[j]>=R)cov++;
else if(l[j]<=R&&r[j]>=L){
Run(k,max(l[j],L),min(r[j],R))b[k]--;
mx=;Run(k,L,R)upd(mx,b[k]);
}
}
s[i]=s[i-];
if(l[i]<=L&&r[i]>=R)upd(ed[i],j),s[c[++cn]=i]++;
else if(l[i]<=R&&r[i]>=L)d[++dn]=i,e[dn]=cn;
}//
for(int i=L;i<=R;i++){
mx=a[i];
for(int j=,k=;j<=dn;j++){
mx+=s[d[j]]-s[d[j-]];
if(l[d[j]]<=i&&r[d[j]]>=i){
mx++;
while(k<dn&&mx>)k++,mx-=s[d[k]]-s[d[k-]]+(l[d[k]]<=i&&r[d[k]]>=i);
if(mx>){
if(s[m]-s[d[k]]<mx)upd(ed[d[j]],m+);
else upd(ed[d[j]],c[e[k]+mx]);
continue;
}
if(l[d[k]]<=i&&r[d[k]]>=i)upd(ed[d[j]],mx<?c[e[k]+mx+]:d[k]);
else upd(ed[d[j]],c[e[k]+mx]);
}
}
}//
}//
Run(i,,m)g[i].push_back((node){v[i],}),g[ed[i]].push_back((node){v[i],-});
for(int i=;i<=m;i++){
for(int j=;j<(int)g[i].size();j++){
int x=g[i][j].x,y=g[i][j].y;
if((vis[x]+y==)^(vis[x]==))num+=y;
vis[x]+=y;
}
printf("%d\n",num);
}
return ;
}//by tkys_Austin;