[YNOI2018]五彩斑斓的世界&CF896E(分块+并查集)
2024-09-02 12:15:50
由于晚上比赛二连(Atcoder&codeforces),外加复习学考,所以暂时没时间写了。
贴个O(n√n)的分块代码,洛谷和cf上都过了,但垃圾bzoj卡不过去,不改了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
int n,m,B,a[N],b[N],pos[N],l[N],r[N],fa[N],mx[N],sum[N],c[][N],tag[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void build(int id)
{
for(int i=l[id];i<=r[id];i++)a[i]=b[find(i)],c[id][a[i]]=;
for(int i=l[id];i<=r[id];i++)fa[i]=i,sum[i]=;
for(int i=l[id];i<=r[id];i++)
if(!c[id][a[i]])c[id][a[i]]=i,b[i]=a[i];
else sum[c[id][a[i]]]+=sum[i],fa[i]=c[id][a[i]];
while(!c[id][mx[id]])mx[id]--;
}
void update(int id,int x,int y,int v)
{
for(int i=l[id];i<=r[id];i++)a[i]=b[find(i)];
for(int i=l[id];i<=r[id];i++)c[id][a[i]]=;
for(int i=x;i<=y;i++)if(b[find(i)]-tag[id]>v)a[i]-=v;
for(int i=l[id];i<=r[id];i++)b[i]=a[i],fa[i]=i;
build(id);
}
void modify(int x,int y,int v)
{
if(pos[x]==pos[y]){update(pos[x],x,y,v);return;}
update(pos[x],x,r[pos[x]],v),update(pos[y],l[pos[y]],y,v);
for(int i=pos[x]+;i<pos[y];i++)
if(v<mx[i]-tag[i]&&mx[i]-tag[i]<*v)
{
for(int j=tag[i]+v+;j<=mx[i];j++)
if(c[i][j])
if(!c[i][j-v])c[i][j-v]=c[i][j],b[c[i][j]]=j-v,c[i][j]=;
else fa[c[i][j]]=c[i][j-v],sum[c[i][j-v]]+=sum[c[i][j]],c[i][j]=;
while(!c[i][mx[i]])mx[i]--;
}
else if(mx[i]-tag[i]>=*v)
{
for(int j=tag[i]+;j<=tag[i]+v;j++)
if(c[i][j])
if(!c[i][j+v])c[i][j+v]=c[i][j],b[c[i][j]]=j+v,c[i][j]=;
else fa[c[i][j]]=c[i][j+v],sum[c[i][j+v]]+=sum[c[i][j]],c[i][j]=;
tag[i]+=v;
}
}
int query(int x,int y,int v)
{
int ret=;
if(pos[x]==pos[y])
{
for(int i=x;i<=y;i++)if(b[find(i)]-tag[pos[i]]==v)ret++;
return ret;
}
for(int i=x;i<=r[pos[x]];i++)if(b[find(i)]-tag[pos[i]]==v)ret++;
for(int i=l[pos[y]];i<=y;i++)if(b[find(i)]-tag[pos[i]]==v)ret++;
for(int i=pos[x]+;i<pos[y];i++)if(v+tag[i]<N)ret+=sum[c[i][v+tag[i]]];
return ret;
}
int main()
{
scanf("%d%d",&n,&m),B=sqrt(n);
for(int i=;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i],fa[i]=i;
for(int i=;i<=n;i++)
{
r[pos[i]=(i-)/B+]=i;
if(!l[pos[i]])l[pos[i]]=i;
}
for(int i=;i<=pos[n];i++)mx[i]=1e5,build(i);
while(m--)
{
int op,x,y,v;scanf("%d%d%d%d",&op,&x,&y,&v);
if(op==)modify(x,y,v);else printf("%d\n",query(x,y,v));
}
}
最新文章
- Thinking in Java——笔记(8)
- SwipeRefreshLayout和RecyclerView滑动冲突的解决
- 使用 jQuery Mobile 与 HTML5 开发 Web App —— HTML5 离线缓存
- 搭建自己的OpenWrt开发环境
- Entity Framework 第三篇 实体特性声明
- LeetCode() Minimun Size Subarray Sum
- linux下USB转串口驱动的安装
- javascript实现暂停
- 自己写的SqlHelper
- [Locked] Strobogrammatic Number &; Strobogrammatic Number II &; Strobogrammatic Number III
- 把图片生成Base64字符串
- 日志收集之kafka
- 单例--iOS
- 利用canvas压缩图片
- 【转】循环冗余校验(CRC)算法入门引导
- 03 整合IDEA+Maven+SSM框架的高并发的商品秒杀项目之web层
- eclipse代码恢复(开发程序代码恢复)
- 一文快速了解MaxCompute
- 四、Java多人博客系统-2.0版本
- 2.9 while循环