题目描述
区间绝对众数
即出现次数>len/2下取整的数
对于区间[L,R]扫一遍，维护一个数x和出现次数s
当前数=x则s+1，否则s-1，若s已为0则把x设为当前数
若区间内存在绝对众数，那么就算用其他的数和其抵消后仍然能剩余
因此最后的x就是可能的绝对众数（当区间内存在时）
推广到本题，设d=100/p下取整，对于线段树内每个区间维护d个可能的强国
显然一个国家在两个区间内都是弱国的话合并后不可能变成强国，因此可能的强国只有这2d个国家
合并一下，若合并后多于d个就把第d+1个去消前d个
原理同上，一个强国一次会消掉至少d个数，全部消完后还有剩余
而题目又允许出现弱国，所以可以这样搞
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
#define file
using namespace std;
char ch;
void get(int &x)
{
x=0;
ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+(ch-'0'),ch=getchar();
}
void put(int x)
{
int a[8],len=0;
if (!x) putchar('0');
while (x) {a[++len]=x%10;x/=10;}
while (len) {putchar(a[len--]+'0');}
}
int a[150001],Tr[600001],n,Q,p,d,tp,i,j,k,l,x,y,z; //Tr<0:1 >0:2
struct type{
int x,s;
inline void clear() {x=s=0;}
};
bool cmp(type a,type b) {return a.s>b.s;}
struct arr{
type a[11];
inline void clear() {int i;fo(i,1,10) a[i].clear();}
void merge(arr b)
{
int i,j,N=0,tot=0;
fo(i,1,d) if (a[i].s) N=tot=i; else break;
fo(i,1,d)
if (b.a[i].s)
{
fo(j,1,N)
if (b.a[i].x==a[j].x)
{a[j].s+=b.a[i].s;break;}
if (j>N)
a[++tot]=b.a[i];
}
else
break;
if (tot)
{
stable_sort(a+1,a+tot+1,cmp);
if (tot>d)
{
fo(i,1,d)
{
a[i].s-=a[d+1].s;
if (!a[i].s)
a[i].x=0;
}
tot=d;
}
}
fo(i,tot+1,10) a[i].clear();
}
} tr[600001],ans;
int merge(int x,int y)
{
if (!x || y<0) return y;
if (x<0) return x-y;
return x+y;
}
void down(int t,int len)
{
int i;
if (Tr[t])
{
if (len>1) Tr[t*2]=merge(Tr[t*2],Tr[t]),Tr[t*2+1]=merge(Tr[t*2+1],Tr[t]);
if (Tr[t]<0)
{
tr[t].clear();
tr[t].a[1]={-Tr[t],len};
}
else
{
fo(i,1,d)
if (tr[t].a[i].s)
tr[t].a[i].x+=Tr[t];
else
break;
}
Tr[t]=0;
}
}
void up(int t)
{
tr[t]=tr[t*2];
tr[t].merge(tr[t*2+1]);
}
void mt(int t,int l,int r)
{
int mid=(l+r)/2;
if (l==r)
{
tr[t].a[1]={a[l],1};
return;
}
mt(t*2,l,mid);
mt(t*2+1,mid+1,r);
up(t);
}
void change(int t,int l,int r,int x,int y,int s)
{
int mid=(l+r)/2;
down(t,r-l+1);
if (x<=l && r<=y)
{
Tr[t]=s;
down(t,r-l+1);
return;
}
down(t*2,mid-l+1);
down(t*2+1,r-mid);
if (x<=mid)
change(t*2,l,mid,x,y,s);
if (mid<y)
change(t*2+1,mid+1,r,x,y,s);
up(t);
}
void find(int t,int l,int r,int x,int y)
{
int mid=(l+r)/2;
down(t,r-l+1);
if (x<=l && r<=y)
{
ans.merge(tr[t]);
return;
}
if (x<=mid)
find(t*2,l,mid,x,y);
if (mid<y)
find(t*2+1,mid+1,r,x,y);
}
int main()
{
freopen("war.in","r",stdin);
#ifdef file
freopen("war.out","w",stdout);
#endif
get(n);get(Q);get(p);d=100/p;
fo(i,1,n) get(a[i]);
mt(1,1,n);
for (;Q;--Q)
{
get(tp);
if (Q<0 || n!=150000)
n=n;
switch (tp)
{
case 1:{
get(x);get(y);get(z);
change(1,1,n,x,y,-z);
break;
}
case 2:{
get(x);get(y);
change(1,1,n,x,y,1);
break;
}
case 3:{
get(x);get(y);
ans.clear();
find(1,1,n,x,y);
fo(k,1,d)
if (!ans.a[k].s)
{break;}
--k;
put(k);putchar(' ');
fo(i,1,k)
put(ans.a[i].x),putchar(' ');
putchar('
');
break;
}
}
}
fclose(stdin);
fclose(stdout);
return 0;
}