题解：P11882 [RMI 2024] 彩虹糖 / Skittlez
Solution
简单题。
众所周知，绝对众数可以通过打擂台（摩尔投票）实现。
所以可以定义二元组
- 如果
col_1=col_2 ，则为(col_1,cnt_1+cnt_2) ； - 否则，如果
cnt_1 < cnt_2 ，为(col_2,cnt_2-cnt_1) ； - 否则，如果
cnt_1>cnt_2 为(col_1,cnt_1-cnt_2) ； - 否则，定义为
(-1,0) 。
我们不需要分析这种运算是否具有交换律和结合律，只需要明白：无论怎么交换和结合这种操作，如果绝对众数存在就一定能被找出来。
所以我们需要处理
这种不可差分的二维信息怎么维护呢？
考虑对第一维进行猫树分治（操作的顺序可以随意调换）。在扫描第一维的过程中，用线段树维护第二维。
注意到信息可以交换，所以可以使用标记永久化，获得更小的常数。
复杂度显然为 看起来太搞笑了，复杂度瓶颈在最后检验时的二维树状数组上。
事实上我感觉一维猫树分治后另一维直接暴力可能也不会太慢。
#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1000+10,MAXM=5e5+10;
int n,q;
int x[MAXM],y[MAXM],xx[MAXM],yy[MAXM],k[MAXM],c[MAXM],ans[MAXN][MAXN];
vector<pair<int,int>> qr[MAXM];
vector<int> upd[MAXM];
struct Z {int col;ll cnt;}fin[MAXN][MAXN];
Z operator +(Z A,Z B) {
if(A.col==B.col) return {A.col,A.cnt+B.cnt};
if(A.cnt>B.cnt) return {A.col,A.cnt-B.cnt};
return {B.col,B.cnt-A.cnt};
}
namespace BIT {
ll tr[MAXN][MAXN];
inline void update(int p1,int p2,const int v) {
for(int p=p1;p<=n;p+=(p&-p)) for(int q=p2;q<=n;q+=(q&-q)) tr[p][q]+=v;
return ;
}
inline ll query(int p1,int p2) {
ll ans=0;
for(int p=p1;p;p-=(p&-p)) for(int q=p2;q;q-=(q&-q)) ans+=tr[p][q];
return ans;
}
};
int ok[MAXN<<2],L[MAXN<<2],R[MAXN<<2];
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
void build(int k,int l,int r) {ok[k]=1,L[k]=l,R[k]=r;if(l!=r) build(lson,l,mid),build(rson,mid+1,r);return ;}
struct INFO {int l,r;Z ad;};
vector<INFO> ad[15][MAXN];
namespace SGT {
Z tag[MAXN<<2],pre[MAXN<<2];
void init(void) {ffor(i,1,n*4) tag[i]=pre[i]={0,0};return ;}
void update(int k,int l,int r,int x,int y,Z ad) {
if(x<=l&&r<=y) return tag[k]=tag[k]+ad,void();
if(x<=mid) update(lson,l,mid,x,y,ad);
if(y>mid) update(rson,mid+1,r,x,y,ad);
return ;
}
void add(int h) {
ffor(i,1,4*n) pre[i]=tag[i];
ffor(i,1,4*n) if(ok[i]) {
if(L[i]==R[i]) fin[h][L[i]]=fin[h][L[i]]+pre[i];
else pre[i<<1]=pre[i<<1]+pre[i],pre[i<<1|1]=pre[i<<1|1]+pre[i];
}
return ;
}
};
void insert(int k,int l,int r,int x,int y,INFO info,int dep) {
if(l==r) return ad[dep][l].push_back(info),void();
if(x<=mid&&y>mid) return ad[dep][x].push_back(info),ad[dep][y].push_back(info),void();
if(x==mid+1) return ad[dep][y].push_back(info),void();
if(y==mid) return ad[dep][x].push_back(info),void();
if(y<=mid) insert(lson,l,mid,x,y,info,dep+1);
else insert(rson,mid+1,r,x,y,info,dep+1);
return ;
}
void solve(int k,int l,int r,int dep) {
if(l==r) {
SGT::init();
for(auto pr:ad[dep][l]) SGT::update(1,1,n,pr.l,pr.r,pr.ad);
SGT::add(l);
return ;
}
solve(lson,l,mid,dep+1),solve(rson,mid+1,r,dep+1);
SGT::init();
ffor(i,l,mid) {
for(auto pr:ad[dep][i]) SGT::update(1,1,n,pr.l,pr.r,pr.ad);
SGT::add(i);
}
SGT::init();
roff(i,r,mid+1) {
for(auto pr:ad[dep][i]) SGT::update(1,1,n,pr.l,pr.r,pr.ad);
SGT::add(i);
}
return ;
}
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>q;
build(1,1,n);
ffor(i,1,q) {
cin>>x[i]>>y[i]>>xx[i]>>yy[i]>>c[i]>>k[i];
insert(1,1,n,x[i],xx[i],{y[i],yy[i],{c[i],k[i]}},1);
BIT::update(x[i],y[i],-k[i]);
BIT::update(x[i],yy[i]+1,k[i]);
BIT::update(xx[i]+1,y[i],k[i]);
BIT::update(xx[i]+1,yy[i]+1,-k[i]);
upd[c[i]].push_back(i);
}
solve(1,1,n,1);
memset(ans,-1,sizeof(ans));
ffor(i,1,n) ffor(j,1,n) qr[fin[i][j].col].push_back({i,j});
ffor(c,1,q) if(qr[c].size()) {
for(auto i:upd[c]) {
BIT::update(x[i],y[i],2*k[i]);
BIT::update(x[i],yy[i]+1,-2*k[i]);
BIT::update(xx[i]+1,y[i],-2*k[i]);
BIT::update(xx[i]+1,yy[i]+1,2*k[i]);
}
for(auto pr:qr[c]) if(BIT::query(pr.first,pr.second)>0) ans[pr.first][pr.second]=c;
for(auto i:upd[c]) {
BIT::update(x[i],y[i],-2*k[i]);
BIT::update(x[i],yy[i]+1,2*k[i]);
BIT::update(xx[i]+1,y[i],2*k[i]);
BIT::update(xx[i]+1,yy[i]+1,-2*k[i]);
}
}
ffor(i,1,n) {ffor(j,1,n) cout<<ans[i][j]<<' ';cout<<'\n';}
return 0;
}