花神游历各国 题解（小清新线段树/树状数组+并查集）
标签：text 线段 display sqrt 技术 ++ 不可 += 特殊
众所周知，这是一道小清新线段树
然而可以用树状数组水过去且跑得飞快
看到区间开方第一反应肯定是线段树懒标记区间修改之类的，但是这个东西似乎确凿不可维护
所以考虑暴力循环单点修改->T飞
于是我们关注一下开方本身的特殊性
我们知道，如果每次向下取整，一个数经过多次操作最终会变成1（或0）
事实上，大概经过 log(logx)次就会变成1
这是什么概念呢？经过博主测试，1e9只要经过五次开方取整就会变成1
那么接下来就能够利用1每次不必再操作优化复杂度
可以维护一个类似链表的结构，指向下一个>1的数，用并查集维护
并查集+树状数组这两种常数极小的结构组合起来简直快的飞起：
蒟蒻第一次上榜有点激动Orz
#include
#include
#include
#includeusing namespace std;
const int L=120|1;
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
typedef long long ll;
const int N=100005;
ll c[N];
int n,m,data[N],fa[N];
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch‘0‘||ch>‘9‘)
{if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘)
{x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
int lb(int x){return x&-x;}
int findf(int x)
{
if(x==fa[x])return x;
fa[x]=findf(fa[x]);
return fa[x];
}
void update(int p,int v)
{
while(plb(p);
}
ll sum(int p)
{
ll res=0;
while(p)res+=c[p],p-=lb(p);
return res;
}
int main()
{
n=read();
for(int i=1;iread(),update(i,data[i]);
m=read();
for(int i=1;i1?i+1:i;
fa[n+1]=n+1;
while(m--)
{
int op=read(),l=read(),r=read();
if(op==1)printf("%lld\n",sum(r)-sum(l-1));
else if(op==2)
for(int i=l;i1))
{
int sqt=(int)sqrt(data[i]);
update(i,sqt-data[i]),data[i]=sqt;
if(data[i]1)fa[i]=findf(i+1);
}
}
return 0;
}
View Code
花神游历各国 题解（小清新线段树/树状数组+并查集）
标签：text 线段 display sqrt 技术 ++ 不可 += 特殊
原文地址：https://www.cnblogs.com/Rorschach-XR/p/11008046.html
评论