首页 > 代码库 > [ CodeVS冲杯之路 ] P2492
[ CodeVS冲杯之路 ] P2492
不充钱，你怎么AC？
题目：http://codevs.cn/problem/2492/
在此先orz小胖子，教我怎么路径压缩链表，那么这样就可以在任意节点跳进链表啦（手动@LCF）
对于查询操作，直接树状数组（以下简称BIT）维护，修改操作就一个个暴力开方搞，再用差值单点更新BIT
不过这样会TLE，要加一点优化对不对，正如开头所说的路径压缩链表
路径压缩链表其实就是个并查集，在普通的链表里，删去两个连续的节点后会是下面这种情况，如删去2,3
当访问 2 的时候，会跳到3，但 3 已经删除了，这就不合法了
于是我们要用路径压缩，搞成下面这种情况
它是不是非常优秀，就按照并查集一样实现，具体参考代码
那么我们想，为什么要搞链表呢？修改的时候直接暴力扫不就行了？
显然 sqrt(1)=1，那么对于 1 的操作不就是无用功？那么记录下来 1 的位置，然后用链表在扫的时候把它跳转掉，因为区间可以是中间的一段，所以要用路径压缩
记得开long long，然后数组多开 1 个，因为若 r 为极限数据，那么跳到最后一个还会往后面跳一个，没开大的话会RE（反正多开一点好一些），记得链表的 f[n+1]=n+1 也要赋值
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 typedef long long LL; 8 using namespace std; 9 10 const int N=100002;11 LL a[N],s[N];12 int f[N],n;13 namespace QuQ14 {15 inline int lowbit(int x)16 {17 return x&-x;18 }19 inline void plus(int x,LL k)20 {21 while (x<=n)22 {23 a[x]+=k;24 x+=lowbit(x);25 }26 }27 inline LL sum(int x)28 {29 LL k=0;30 while (x)31 {32 k+=a[x];33 x-=lowbit(x);34 }35 return k;36 }37 }38 namespace OvO39 {40 inline LL read()41 {42 char ch=getchar();43 LL k=0;44 while (ch<‘0‘||ch>‘9‘) ch=getchar();45 while (ch>=‘0‘&&ch<=‘9‘)46 {47 k=k*10+ch-‘0‘;48 ch=getchar();49 }50 return k;51 }52 inline void write(LL x)53 {54 if (x>9) write(x/10);55 putchar(x%10+‘0‘);56 }57 }58 inline int find(int x)59 {60 return f[x]==x?x:f[x]=find(f[x]);61 }62 int main()63 {64 int m,i,l,r;65 LL x;66 n=OvO::read();67 for (i=1;i<=n;i++)68 {69 s[i]=OvO::read();70 QuQ::plus(i,s[i]);71 f[i]=i;72 }73 f[n+1]=n+1;74 m=OvO::read();75 while (m--)76 {77 x=OvO::read();78 l=OvO::read();79 r=OvO::read();80 if (l>r) swap(l,r);81 if (x)82 {83 OvO::write(QuQ::sum(r)-QuQ::sum(l-1));84 putchar(‘\n‘);85 }86 else for (l=find(l);l<=r;l=find(l+1))87 {88 x=s[l];89 x-=s[l]=sqrt(s[l]);90 if (s[l]==1) f[l]=find(l+1);91 QuQ::plus(l,-x);92 }93 }94 return 0;95 }
[ CodeVS冲杯之路 ] P2492
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。