万古神犇LXL，数据结构碾众生！
即使是蒟蒻也想变强啊..
luogu P3987 我永远喜欢珂朵莉~（这是题目名称！）
题目大意：
有一个长为n的非负数序列A，支持以下两个操作：
- 1 l r x : 把区间[l,r]中所有x的倍数/x
- 2 l r : 查询区间[l,r]的和
数据范围：
\(1 \le n , m \le 100000\)
\(0 \le A_i \le 500000\)
\(1 \le x \le 500000\)
题解：
首先，这道题的突破口在这里：
一个数的约数个数不会太多。虽说上界\(O(\sqrt n)\),但实际上远没有那么多。500000以内只有大概200个左右。当对值域进行限制的时候，很可能就与约数个数相关。尤其是，本题中还有很明显的x的倍数÷x的操作，可以考虑对每个可能的约数进行维护。
鉴于单点修改，区间求和是\(O(\log n)\) 的，而一个数最多被除\(O(\log n)\)次，总复杂度\(O(n\log^2 n)\)这并不是制约复杂度的关键。而且，如果对于整个数列或分块以后的整块（本质上是一个“整体”）维护整体的信息的话，这题根本不可做了。必须找出需要被除的数，才能维护整个数列。现在问题是，如何快速找到需要被除的数。即，如何快速找到序列中x的倍数。可以考虑对所有\(x\in (2,500000)\)进行维护。对于每个约数，维护一棵平衡树，存储数列中它的倍数的下标。当进行区间除的时候，在对应的平衡树中找到下标在\([l, r]\)之间的子树，进行dfs，并删掉所有操作进行后不再是x倍数的数的下标。这个过程中可以顺便维护数列值的变化。当然，并不需要建出所有的平衡树，只对查询的x建树就行了。
说来惭愧，我这道题在看了lxl的题解后还改了好几天。我从这道题吸取的经验有以下几点：
- 当你的板子检查了很多很多遍都没发现问题时，很可能是main函数写错了（捂脸
- 各种最大值一定要弄清楚，例如我写题的时候就把值域最大值当成了n。
- 板子是可以根据自己的需要而改动的。如本题中平衡树并不需要维护size。
当然YNOI的毒瘤题需要一点卡常的小trick，相信大家都会，不再赘述。
我的代码：
1 |
|
luogu P5068[Ynoi2015]我回来了
题目描述
珂朵莉给你一个无向图，每次查询的时候给一堆二元组\((x_i,y_i)\) 求图中有多少个点u与至少一个这次询问给出的二元组\((x_i,y_i)\)满足 \(dist(u,x_i)\le y_i\)，dist表示这两个点在图中的距离 如果不连通\(dist = \inf\)
输入输出格式
输入格式：
- 第一行三个数表示n，m，q
- n表示顶点个数，m表示边数
- 之后m行每行两个数x，y表示这两个点之间连有一条边~，边权都为1
- 之后q次询问，每个询问先给你一个数a
- 之后a行每行两个数，x，y，表示一个二元组
- n <= 1000 , m <= 100000 , q <= 100000
- a的和 <= 2100000
输出格式：
- q行，每行一个数表示这次询问的答案
题解：
这道题大概是YNOI中最良心的一道题？(雾 然而我也没做出来
首先，我们可以想到，这题大概要预处理，然后用接近\(O(1)\)的时间回答每个二元组询问。考虑题目中，每一个点即使满足所有要求也只被计算一次贡献，而每个二元组之间又是相互独立的，所以我们需要一个资瓷快速集合取并，快速求集合元素数目的数据结构——这不就是\(\text{bitset}\)嘛。所以，我们尝试，令\(f(u,i)\)为\(dist(u,v)\le i\)的v的集合，则对于每次询问，将所对应的\(f\)集合取一个并就好了。现在，问题转化为如何求f集合。本题的时空限制十分诡异，会让人误以为标算的复杂度是错的（然鹅实际跑得飞快）其实暴力计算f就可以了~~
- 首先，跑n次bfs，计算出所有顶点对之间最短路。时间\(O(n(n+m))\)
- 然后，用已知的信息暴力更新f。设w为bitset的位宽，时间\(O(n^3/w)\)
- （逃
最后，毒瘤lxl卡了链式前向星，可以使用vector（因为空间够用，所以我直接开了邻接矩阵）
注意，输入存在重边。
所以，这道题我们就做完啦（撒花！
我的代码
（我以为这题一定很卡常，所以代码稍微毒瘤了一点）：
1 |
|
luogu P5072[YNOI2015]盼君勿忘
题目描述
珂朵莉给了你一个序列，每次查询一个区间[l,r]中所有子序列分别去重后的和mod p
输入输出格式
输入格式：
- 第一行两个数\(n,m\)
- 第二行\(n\)个数表示这个序列\(A\)
- 之后\(m\)行，每行三个数\(l,r,p\)表示查询的区间与模数
- 对于\(100\%\)的数据，\(n,m <= 10^5\),\(A_i,p <= 1000000000\)
输出格式：
- \(m\)行，每行输出一个数表示答案
题解
Orz lxl...由乃OI真的毒瘤。。。
我从不抄题解，我只是题解的搬运工。真的不会做，瞎写一点儿吧。
看到这题，没修改操作，数据范围1e5，可以想到这是个莫队题。然后我就不会了。
看到这样的题，我们暴力考虑每个区间显然是不现实的。我们转而考虑每个数对答案的贡献。对于一个数，它被计算到的次数可以这么计算：
对于一个区间\([l..r]\)，它的非空子序列个数显然为\[2^{r-l+1}-1\]个。不包含x的子序列有\[2^{r-l+1-cnt[x]}-1\]个。所以，x一共被计算了\(2^{r-l+1}-2^{r-l+1-cnt[x]}\)次。
所以，我们用\(cnt[x]\)维护x在当前区间的出现次数，莫队维护cnt，修改的同时暴力维护和。。。这就可以做到\(O(n\sqrt n)\)了
上面的假做法只适合模数不变的情况。。。我们考虑模数会变化该怎么做。
手动划重点！以下内容的思想很重要！
考虑以\(\sqrt n\)为界限分类讨论。对于出现次数小于\(\sqrt n\)的数，他们的出现次数只有\(\sqrt n\)种。对于出现次数大于等于\(\sqrt n\)的数，这样的数最多只有\(\sqrt n\)种。所以我们对于每个小于等于\(\sqrt n\) 的出现次数x，维护出现次数=x的数之和，对于出现次数\(\geq \sqrt n\)的数，用一种数据结构维护它们组成的集合。\(\text{STL unordeded_set}\)是个好东西啊。虽然考试不让用这样就可以做到\(O(n\sqrt n)\)求解问题啦。
最后还有一个小问题——如何快速求2的幂？模数动态改变，每次必须重新计算。有一种\(O(\sqrt n)\)预处理，\(O(1)\)查询的处理方法，正好适合本题。
设\(T=\lfloor\sqrt n\rfloor\),则\(C^{x}=C^{\lfloor x/T \rfloor} * C^{x\mod T}\) 。这样，只需要预处理\(C^1, C^2, C^3....C^T\)和\(C^T, C^{2T}....C^{T*T}\) 即可。
我的代码：
(卡常的血泪史。。。)另外，好像对于值域比较大的情况，它会输出负数，现在暂时没找到原因。还有，膜运算真的太慢啦！去掉四个膜运算，运行时间几乎-1s。。
1 |
|
luogu P3674小清新人渣的本愿
题目描述
给你一个序列a，长度为n，有m次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是否可以选出两个数它们的和为x，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作1,2,3
选出的这两个数可以是同一个位置的数
输入输出格式
输入格式：
- 第一行两个数\(n,m\)
- 后面一行\(n\)个数表示\(a_i\)
- 后面\(m\)行每行四个数\(opt\ l\ r\ x\)
- \(opt\)表示这个是第几种操作，\(l,r\)表示操作的区间，\(x\)表示这次操作的\(x\)
输出格式：
- 对于每个询问，如果可以，输出\(\text{hana}\)，否则输出\(\text{bi}\)
题解
这题还是挺良心的比上一题良心多了 瞎说毒瘤lxl怎么会出良心题
没修改+1e5+lxl=膜队。
所以我们考虑怎么膜队维护。
我们首先肯定要维护所有数的出现次数。然后怎么做？
考虑暴力：对于每个可能成为答案的数，查询对应的另一个数是否存在。这个大概没法用什么数据结构优化了，所以考虑神奇的\(\text{bitset}\)。用\(\text{bitset}\)维护每个数是否出现，我们发现：
- 对于询问1，若存在k和k+x，则对应着\(\text{S&(S<<x).any()==true}\) 。
- 对于询问2，若存在\(a+b=x\),即\(a-(-b)=x\)。对于负数，我们不好维护，所以用处理负下标的一般方法，转化成\(a-(-b+N)=x-N\)。（此处N是一个较大的整数）这样，用另外一个\(\text{bitset}\)，对于每个出现的\(k\)，令对应的\((-k+n)\)下标处的值为1就可以了。另外，\(\text{bitset}\)的移位运算会将\(\text{int}\)强转成\(\text{size_t}\)，当移位数为负数的时候会出锅。所以要手动把上面的左移改成右移，移位数取反。
- 对于询问3，我们发现我们用\(\text{bitset}\)没法很好的维护了。所以暴力枚举因子，判断是否存在,可以发现这并不是复杂度的瓶颈。这样做是正确的......
我的代码：
您看我如果不卡常的话码风还是挺正常的嘛
1 |
|
luogu P4688[YNOI2016]掉进兔子洞
题目描述
给定一个长度为n的数列，有m次询问。每次询问给出三个区间，询问若从这三个区间一起删数，一直删到三个区间没有共同的数为止，最后这三个区间一共剩下的数的数量。（询问之间互相独立）
题解
这道题的话，首先，还是经验公式：
没修改+1e5+lxl=膜队。
所以考虑怎么膜队。
首先通过补集转化，问题转化为三个区间共同出现的数的数量。既然是膜队，就要对每个区间分别处理。现在我们需要维护的信息就十分明确了：维护资瓷快速求交集的区间出现元素。这用数据结构并不好维护，所以考虑万能的\(\text{bitset}\)。现在问题来了：\(\text{bitset}\)只能对于每个元素，维护是否出现过，并不能维护出现多少次。此时情况开始变得辣手起来。。。
能不能通过某种手段，使得\(\text{bitset}\)中留够足够的空间使得每个相同的数能够连续存储在一段空间中？可以！我们只需要在离散化时不去重就可以了！在存储时，令\(x+cnt[x]-1\)这一位为1，就可以了。（我在代码中是采用\(\text{shadowice1984}\)大佬的方法，令离散化之后的值为数列中小于等于该数的数的个数，就令\(x-cnt[x]+1\)这一位为1。显然这两种方法是基本相同的。那么，我们就做完啦！
才不是呢！lxl的题怎么能这么轻易做完？
我们发现我们的最终结果是保存在\(1e5个\)\(\text{bitset}\)里面的。算一波空间，会发现我们开不下。。。所以，我们的算法错了么？考虑充足的时限，我们把询问分成三次处理。这里还有一个避免分类讨论的trick，就是首先把询问储存下来，每次查询时将莫队的询问数组清零，并将当前处理的区间复制到莫队的数组里。这样能使代码简洁许多，并提高可复用性。
我的代码：
1 |
|
Luogu P3793由乃救爷爷
题目大意：
随机数据下大数据RMQ. ## 题解 不知道为啥暴力建笛卡尔树dfs查会那么快...踩了lxl的标算... 万古神犇lch（大声）！ 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80// luogu-judger-enable-o2
typedef long long unsigned int uint64_t;
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
void srand(unsigned x)
{
using namespace GenHelper;
z1=x;
z2=(~x)^0x233333333U;
z3=x^0x1234598766U;
z4=(~x)+51;
}
int read()
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
const int maxn=2e7+1000;
const int INF=0x7fffffff;
int a[maxn],ls[maxn],rs[maxn],root;
inline void init(int n)
{
static int stack[maxn];
int top=0;
a[0]=-INF;
for (int i=1;i<=n;++i)
{
while (top && a[stack[top]]<=a[i]) ls[i]=stack[top--];
rs[stack[top]]=i;
stack[++top]=i;
}
root=stack[1];
}
inline uint64_t query(int l,int r)
{
for (int x=root;;x=x<l?rs[x]:ls[x])
if (x>=l && x<=r) return a[x];
}
int main()
{
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
srand(s);
for (int i=1;i<=n;++i) a[i]=read();
uint64_t ans=0;int l,r;
init(n);
for (int i=1;i<=m;++i)
{
l=read()%n+1;
r=read()%n+1;
ans+=l>r?query(r,l):query(l,r);
}
printf("%llu",ans);
}
Luogu P3934[Ynoi 2016]炸脖龙/Nephren Ruq Insania
和《相逢是问候》差不多，就不放题解了... 注意写法边界问题就好。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
using std::pair;
using std::make_pair;
typedef long long ll;
const int maxn=5e5+100;
const int maxp=2e7+100;
ll c[maxn];
int n,m,a[maxn],phi[maxp];
inline void add(int p,int x)
{
for (;p<=n;p+=p&-p) c[p]+=x;
}
inline ll query(int p)
{
ll ans=0;
for (;p;p-=p&-p) ans+=c[p];
return ans;
}
void sieve(int n)
{
static int v[maxp],prime[maxp],cnt;
phi[1]=1;
for (int i=2;i<=n;++i)
{
if (!v[i])
v[i]=i,phi[i]=i-1,prime[++cnt]=i;
for (int j=1;j<=cnt;++j)
{
int t=prime[j];
if (t*i>n || t>v[i]) break;
v[i*t]=t;
phi[i*t]=phi[i]*(i%t?t-1:t);
}
}
}
inline pair<int,bool> qpow(ll a,ll b,const int p)
{
ll ans=1;
bool gr=false;
if (ans>=p) ans=ans%p,gr=true;
if (a>=p) a%=p,gr=true;
for (;b;b>>=1)
{
if (b&1) ans=ans*a;
if (ans>=p) ans=ans%p,gr=true;
a=a*a;
if (a>=p) a%=p,gr=true;
}
return make_pair(ans,gr);
}
inline pair<ll,bool> dfs(int pos,int depth,int limit,const int p)
{
ll t=query(pos);
if (t%p==0) return make_pair(0ll,true);
if (t==1) return make_pair(1,false);
if (depth==limit) return make_pair(t%p,t>=p);
pair<ll,bool> pr=dfs(pos+1,depth+1,limit,phi[p]);
ll exp=pr.first;
if (pr.second) exp+=phi[p];
return qpow(t,exp,p);
}
inline int query(int l,int r,int p)
{
int depth=r-l+1;
return dfs(l,1,depth,p).first%p;
}
signed main()
{
// freopen("testdata.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%lld%lld",&n,&m);
sieve(2e7);
for (int i=1;i<=n;++i)
scanf("%lld",a+i),add(i,a[i]-a[i-1]);
for (int i=1,l,r,x,opt;i<=m;++i)
{
scanf("%lld%lld%lld%lld",&opt,&l,&r,&x);
if (opt==1)
add(l,x),add(r+1,-x);
else printf("%lld\n",query(l,r,x));
}
}
Luogu P5354[Ynoi2017]由乃的OJ/睡觉困难综合征
题意
有一棵无根树。每个结点有一个运算符（\(\mathrm{and \ or \ xor}\)中的一种）和一个权值。要求进行如下两种操作之一：
* \(1\ u,v,k\)：令一个\([0,k]\)之间的正整数\(val\)经过从\(u\)到\(v\)的简单路径。每经过一个标有算符\(\mathrm{opt}\)和权值\(x\)的结点，\(val\)就变成\(val \ \mathrm{opt}\ x\).输出最大的可能结果。 * \(2\ u,\mathrm{opt},val\)将\(u\)的操作改为\(\mathrm{opt}\),权值改为\(val\)。
其中，\(n,m\le 10^5 ,k \in [0,64]\)
题解
神仙题，蒟蒻不会/kel/kel
我们考虑链上的情况，做法是维护一个全0和全1的真值表，然后从高到低按位贪心。把它搬到树上，带修改，多次链询问，咋做啊？树剖嘛！然后呢？...
考虑维护什么信息才能得到路径上的真值表。不同位运算没有交换律，所以我们必须按照原顺序对运算进行处理..但是，一条树上路径可以拆分成\(u\rightarrow lca\)和\(lca\rightarrow v\)的两部分，一条是逆着dfs序，一条是顺着dfs序。我们考虑用线段树维护dfs序上区间正序和逆序执行操作的表...然后我们按照u到v路径的顺序查询就可以了。如果按位操作实现线段树父子结点之间的转移的话，总复杂度就是\(O(nk\lg^2n)\)，显然过不了。所以我们用位运算实现64位一起转移，就可以做\(n\lg^2 n\)了。
代码风格还可以吧
1 | // luogu-judger-enable-o2 |