几道水题的题解

这篇文章包含了这几道简单题的题解:

逆序排列

给出2个数nk,求1~n的全排列中,逆序数为k的排列有多少种。每个测试点包含T组数据。

1 \leq T \leq 10000, 2 \leq n \leq 1000, 0 \leq k \leq 20000

1n的全排列有n!个,每个测试点的数据组数很多。考虑动态规划。

1296 有限制的排列 一样,假如以“当前考虑到1N的全排列的第i位,且逆序对数为j的排列个数”来定义状态d[i][j],必然会困于如何去重。即使找到去除重复数字的方法,也会导致时间复杂度偏高。

因此我们这样简化状态:定义d[i][j]1i的全排列中,逆序对数为j的排列数。可以发现d[n][j]仍然包含了所需要的状态。

如何由1(i-1)的全排列转移到1i的全排列?怎么保证没有重复的数字?假如新排列第i位是j,这些新排列和1(i-1)的全排列的关系是什么?

借鉴 1296 有限制的排列 的思想(这两道题的在思想上很相像),我们可以把每一个1(i-1)的全排列通过以下方式变成一个长度为i,且最后一位为j的全排列:

  1. 将原排列中,大于等于j的数加上1;
  2. 在最后添上j

可以发现每个1(i-1)的全排列都可以转化为各不相同的长度为i,且最后一位为j的全排列 。(从数学上理解,最后一位确定,前i-1位的排列数为(i-1)!,也就是1(i-1)的全排列个数。)

在理解上述内容的基础上,我们可以得到状态转移方程:

d[i][j]=\sum_{k=1}^i d[i-1][j-(i-1-k+1)] = \sum_{k=1}^i d[i-1][j-(i-k)]

在给第i位填上k后,前面大于ki-k个数就会和k构成逆序对。因此需要满足在转移之前有j-(i-k)个逆序对。注意,这里计算的大于k的个数,是指新排列中大于k的个数。即在长度为i-1的原排列中大于等于k的个数。

由于频繁求区间和,可以考虑维护前缀和。长度为i的全排列的状态只与长度为i-1的全排列的状态有关,所以考虑滚动数组。

时间复杂度O(nk+TlogT)

代码如下:

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const long long maxn=1000,mod=1e9 + 7;
long long n,k,done=1;
long long ans[10*maxn+5];
long long sum[2][20005];
struct qst{
long long n,k,id;
}Q[maxn*10+5];
inline void read(long long &x){
x=0;char c;long long f=1;
do{
c=getchar();if(c=='-')f=-1;
}
while(c>'9'||c<'0');
do{
x=x*10+c-'0';c=getchar();
}
while(c>='0'&&c<='9');
x*=f;
}
inline long long max(long long a,long long b){
return a>b?a:b;
}
long long d[2][20005];
void work(){
d[0][0]=1;
sum[0][0]=1;
for(register int i=1;i<=k;++i){
    sum[0][i]=1;
}
for(register long long i=1;i<=n;++i){
for(register long long nk=0;nk<=k;++nk){
d[i&1][nk]=0;
d[i&1][nk]=(sum[(i-1)&1][nk]-(nk-i>=0?sum[(i-1)&1][nk-i]:0)+mod)%mod;
if(i==Q[done].n&&nk==Q[done].k){
ans[Q[done++].id]=d[i&1][nk];
}
sum[i&1][nk]=((nk?sum[i&1][nk-1]:0)+d[i&1][nk])%mod;
}
}
}
inline bool cmp(qst a,qst b){
if(a.n!=b.n)return a.n<b.n;
return a.k<b.k;
}
int main(){
long long T;
read(T);
for(register long long i=1;i<=T;++i){
read(Q[i].n);
read(Q[i].k);
n=max(n,Q[i].n);
k=max(k,Q[i].k);
Q[i].id=i;
}
sort(Q+1,Q+1+T,cmp);
work();
for(register long long i=1;i<=T;++i){
printf("%lld\n",ans[i]);
}
return 0;
}

最长递增路径

一个无向图,可能有自环,有重边,每条边有一个边权。你可以从任何点出发,任何点结束,可以经过同一个点任意次。但是不能经过同一条边2次,并且你走过的路必须满足所有边的权值严格单调递增,求最长能经过多少条边。

1 \leq N \leq 50000, 0 \leq M \leq 50000, 0 \leq W \leq 10^9

有点像最长上升子序列,只不过是在图上。

考虑将每条无向边拆成两条有向边,按照边的大小排序,由于一条路径走过后不能再走,所以没有后效性。

每次从边a转移到边b,需要满足两个条件:

  1. a的终点是b的起点。
  2. a的长度必须严格小于b的。

考虑用数组maxb[]保存每个节点作为终点的,已经走过的最长的边数。那么通过某条边从一个点u走向另一个点v时,可以用maxb[u]+1来更新maxb[v]。为了满足第二点,我们可以以边长为标准分段,将某几条长度相同的边处理完之后,再一起更新这些边更新过的maxb[]

时间复杂度O(mlogm)

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int maxn=5e4;
struct line{
int u,v,w;
}l[maxn*2+5];
int ans;
int d[maxn*2+5],maxb[maxn+5];
inline void read(int &x){
x=0;char c;int f=1;
do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
inline bool cmp(line a,line b){
return a.w<b.w;
}
int n,m;

int main(){
read(n);read(m);
for(register int i=1;i<=m;++i){
read(l[i].u);read(l[i].v);read(l[i].w);
l[i+m].w=l[i].w;
l[i+m].u=l[i].v;
l[i+m].v=l[i].u;
}
sort(l+1,l+1+2*m,cmp);
int lst=1;
for(register int i=1;i<=2*m;++i){
if(l[i].w!=l[lst].w){
for(register int j=lst;j<i;++j){
maxb[l[j].v]=std::max(maxb[l[j].v],d[j]);
}
lst=i;
}
d[i]=maxb[l[i].u]+1;
if(d[i]>ans)ans=d[i];
}
printf("%d\n",ans);
return 0;
}

选数字

当给定一个序列a[0],a[1],a[2],…,a[n-1] 和一个整数K时,我们想找出,有多少子序列满足这么一个条件:把当前子序列里面的所有元素乘起来恰好等于K。 每个测试点包含不超过20组数据,1 \leq n \leq1000,2 \leq K \leq 100000000

很显然是一道动态规划题。

读入一个数字,就可以用它 与 前面的数字能构成的数 来构成新的数(或者给已有的数增加方案数)。这算是最普通的做法。

给出一种优化:

  1. 读入a[i]时,假如k \bmod a[i]\ne0,则直接忽略,读入下一个数字。
  2. a[i]与之前已经生成的某个数x构成新的数时,若k \bmod (x*a[i])\ne0则跳过。

这样我们就可以保证,所有存入的数都是尽可能对答案有帮助的。因为假如一个数不能整除k,必然不可能对答案造成影响。

a[i]与已有的数来更新新的数时,应该将所有的修改都保存起来,等到更新完了之后再应用更新。什么意思呢?假如读入了一个数3,之前已经有了{2,6,18}这三个数,且构成这三个数的方案数分别为{1,2,3}。由我们的推算可知,加入3后,可以由2*3来使构成6的方案数加1,由6*3使构成18的方案数加1,由18*3使构成54的方案数加1。加上3本身,处理之后的已有数字和方案数分别为:{2,3,6,18,54}{1,1,3,4,1}。但是如果我们边处理边更新,会导致同一个3被重复计算。给6的方案数加1后,新增的这个已经用过3的方案,又与3一起更新了18的答案。所以应该把每次要修改的操作保存起来,把所有的待更新数更新完毕后,再应用修改到方案数组中。

由于k较大,可能出现的数字不定,所以可以通过STL map来作为数组。

时间复杂度大概是O(n log k)

#include<cstdio>
#include<map>
using std::map;
const long long maxn=1e3;
const long long mod=1000000007;
long long n,k;
long long a[maxn+5];
map<long long,long long>d;
map<long long,bool> ment;
long long mentd[maxn+5];
struct addo{
long long to,val;
addo(long long to=0,long long val=0):to(to),val(val){}
}add[maxn+5];
inline void read(long long &x){
x=0;char c;long long f=1;
do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
void work(){
for(register long long i=1;i<=n;++i){
read(a[i]);
if(k%a[i]!=0)continue;
long long lmentd=mentd[0],tadd=0;
for(register long long j=1,y;j<=lmentd;++j){
if(k%(y=a[i]*mentd[j])!=0)continue;
add[++tadd]=addo(y,d[mentd[j]]);
if(!ment[y]){
mentd[++mentd[0]]=y;
ment[y]=true;
}
}
for(register long long j=1;j<=tadd;++j){
d[add[j].to]+=add[j].val;
d[add[j].to]%=mod;
}
d[a[i]]++;
d[a[i]]%=mod;
if(!ment[a[i]]){
mentd[++mentd[0]]=a[i];
ment[a[i]]=true;
}
}
printf("%lld\n",d[k]);
}
int main(){
long long T;
read(T);
while(T--){
read(n);read(k);
work();
if(T){
ment.clear();
mentd[0]=0;
}
}
return 0;
}

整数划分

将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。

1 \leq N \leq 50000

当成一个0/1背包问题,1N每个数是一件物品,背包的容积为N。把普通背包(求最大价值)改为求价值之和即可。

但是这种做法的时间复杂度为O(N^2),很显然过不了此题的数据范围。

考虑用g[i][j]表示考虑用i个数构成j的方案数。要求用的数各不相同,所以应该保证构造的数不出现重复。

g[i][j]表示用j个数构成i的方案数,由于每个数各不相同,最多的数的个数m满足(1+2+...+m=n)。计算得知m_{max}=316

i个数字来组成j,假如不选择数字1,那么方案数为g[i][j-i],也就是把构成j-ii个数每个都加上1;假如要选择数字1,为了保证前面没有数字1(题目要求所有数不相同),我们需要把前面i-1个数加上1,再给最后一位放一个1。方案数就是g[i-1][j-i](前i-1位构成j-i)。

选择1和不选择1,包含了所有的情况。

于是我们得到状态转移方程:

    \[g[i][j]=g[i-1][j-i]+g[i][j-i].\]

答案就是\sum_{i=1}^{316} g[i][n].

代码:

#include<cstdio>
#include<cmath>
const long long mod=1e9+7;
const long long maxn=5e4;
long long g[320][maxn+5];
long long ans;
long long n,m;
int main(){
    scanf("%lld",&n);
    g[0][0]=1;
    for(register int i=1;i<=319;++i){
        for(register int j=i;j<=n;++j){
            g[i][j]=(g[i][j-i]+g[i-1][j-i])%mod;
        }
    }
    for(register int i=1;i<=319;++i){
        ans+=g[i][n];
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
} 

求解差分约束系统

差分约束系统是一个N元一次不等式组,由多组形如x_i-x_j \leqslant c_k的不等式组成。一个差分约束系统要么无解,要么有无数组解。

Part 1 前置技能

在了解如何判断一个差分约束系统是否有解,或者求出它的一组解之前,我们需要先掌握它的前置技能。

  • 图论基本概念
  • 求单源最短/长路的方法

讲解图论的算法书籍都会讲解单源最短路的求法。在边权非负时,我们通常使用 Dijkstra 算法或 Bellman-Ford算法(以及它们的堆/队列优化算法)。Dijkstra算法不能处理负权存在时的情况,也不能求出单源最长路。Bellman-Ford算法及其队列优化的SPFA算法可以处理边带负权的情况,于是可以通过将边权取相反数的方法求出单源最长路。(见这里Bellman-Ford算法及其队列优化的SPFA算法都可以判断图中是否存在负环,并且会在d[x]>d[y]+w(y,x)时用y点更新d[x]

在单源最短路算法结束后,假如图G(V,E)中没有负环,那么必有:

\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)

在你搞清楚上面两种SSSP问题求解的算法之后,我们就可以通过以下方式判断负环:

对于Bellman-Ford算法:

每次操作后,总会有一个点收敛。如果没有负环,经过n-1轮迭代后必然不会再有点的路径长度被更新。如果迭代n-1轮后仍然有点的距离可以被更新,那么说明一定有负环。

对于SPFA算法:

假如在用算法进行处理时,一个点的最短路径经过的边数已经大于n-1(即必然重复走了很多边和点),那么说明一定有些点可被重复走过,且重复经过这些点之后可以使距离更小。也就是说,图里有负环。使用一个数组cnt[]记录每个点当前所求最短路经过了多少边就可以解决这个问题。方法是在用x更新y时,令cnt[y]=cnt[x]+1,并判断是否cnt[y] >  n-1

Part 2 求解差分约束系统

在理解Part 1的内容后,我们就可以用它来求解差分约束系统了。

如前所述,差分约束系统中的不等式形式是:

x_i-x_j \leqslant c_k

(例如x_2 - x_1 \leqslant 6)

而一个没有负环的图在跑完单源最短路算法后,满足:

\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)

那么我们能否利用这个形式上的共同性来将求解差分约束系统的问题转化为图上的问题,然后利用图论算法求解?

当然可以。设有图G(V,E),对于差分约束系统中的每组关系 x_i-x_j \leqslant c_k(i,j \in V),我们从j点向i点连接一条权值为c_k的有向边。

假如从这个图的某点出发的单源最短路径为d[i](i \in V),满足 \forall i,j \in V , d[i] \leqslant d[j]+w(j,i) ,那么这个差分约束系统必然是有解的,d[i]就是其中一组解。如果有一组解\{ x_1,x_2,...,x_n \},那么\{ x_1+k,x_2+k,...,x_n+k \} (k \in \mathbb{R}  )也必然是一组解。即它有无数组解。

假如这个图有负环,那么无论如何都有点不满足d[i] \leqslant d[j]+w(j,i)。所以这个不等式组必然没有解。

那假如这个图根本就没有联通呢?只要在每个联通块内不存在负环,那么它也是有解的。我们当然可以对每一个联通块都查找一次负环,但这样太繁琐了。(还要用并查集维护每一块的大小和联通关系)怎么解决?

由上面的推导可以知道,只要一个差分约束系统是有解的,那么它必然有无数组解。我们可以假设它有一组元素均小于等于p的解(p=0则代表求出一组均为负数的解),然后构造一组新的不等式组:

x_i - x_0 \leqslant 0

也就是从点0连一条到点i的权值为0的有向边。

并且令:

d[0]=p

那么我们就可以把这个图联通起来一次跑过了。

Part 3 变形的处理

我们已经能够处理形如x_i-x_j \leqslant c_k的情况了。那如何解决由形如x_i-x_j \geqslant c_k的不等式构成的差分约束系统问题?方法有二:

Way 1 数学变换

很容易将 x_i-x_j \geqslant c_k 变形为x_j-x_i \leqslant -c_k。然后就可以按照之前的步骤求解。(注意Dijkstra算法不可处理带负边权的图)

Way 2改求最长路

对于一个没有正环(走一次边权和为正值)的图,我们可以求解出它每个点从某点出发的单源最长路经d[]

那么一定有:

\forall i,j \in V , d[i] \geqslant d[j]+w(j,i)

同样的,对于不等式 x_i-x_j \geqslant c_k ,我们连一条从ji的边权为c_k 的有向边。可以设虚点使图联通。假如这个图有正环,那么说明该不等式组无解。反之则有解。

求最长路就只能用Bellman-Ford算法(或其队列优化算法SPFA)了。找正环的方法同负环一样。

需要注意的是,如果我们通过计算最短路来求解查分约束系统,那么其求得的值是满足约束条件的最大值。因为最后\forall i,j \in V,d[i] \leqslant d[j] +w(j,i),也就是说每个点满足的是上界条件。如果用最长路来求解,则求解出的答案是满足条件的最小值,理由同上。

有些时候,我们不需要求解,或者在求解之前要先判断整个图的连通性,可以先从一个虚点向每个点连一条线使得图联通,即使添加这个虚点而增加的条件是我们不需要的。然后再不考虑虚点求解。

你可以尝试这几个题(来自李煜东等的书籍推荐):

1.P2868 [USACO07DEC]观光奶牛Sightseeing Cows

2.UVA1723 Intervals

3.P4878 [USACO05DEC] 布局

参考资料:

What can stop me?

前两天和我妈吃饭,她提起一个问题:我还要不要继续学奥赛。

其实我并不觉得奥赛让我成绩怎么退步了。反而在奥赛班里年级排名还比以前上升了很多。

但是她觉得我压力太大了。

其实我自己也还不这么觉得。

所以这些东西其实都不能让我停下手上的奥赛。

但是

这段时间隐约发现自己要秃了。

今天给新学奥赛的学妹带了一瓶洗洁精。晚上回家看到她给我发的QQ消息如下:

我现在觉得,我要是在比赛之前没学奥赛了,肯定不会是因为压力。

而肯定会是因为我怕秃头。

题解 P1494 【[国家集训队]小Z的袜子】

看了一下题解里的大佬,好像都用的莫队或者分块维护平方和…

其实用不着维护平方和。

从头开始说吧。

求什么

对于每个询问qq包含q.l,q.r),我们要求出任取两个袜子颜色相同的概率。假设在区间[l,r]取到颜色为i的袜子的概率为P(l,r,i),那么要求的就是\sum_{i=1} ^{n} P(q.l,q.r,i)

怎么求

那么对于任意的L,R,i,如何计算P(L,R,i)?假设在[L,R]i袜子的个数为n_i,根据数学知识,要取到两只i,首先要取第一只i颜色的袜子。因为有n_i只袜子都是i颜色的,所以取第一只i袜子的方案数为n_i。然后再取第二只i颜色的袜子。由于已经取了1只i颜色的袜子,就只剩下i-1只可选了。这样的排列数有n*(n-1)个。

计算概率时有顺序用排列,无顺序用组合,因为我们只关心两只袜子是否颜色相同,所以这道题中选袜子的顺序是没有影响的。而刚刚计算的只是排列数,每种组合方式被计算了2次(选第1,3只白袜和选第3,1只白袜是一样的)。所以要除以2。
即选到两只i颜色的袜子的方案数n_i(n_i-1)/2.

[L,R]内,有R-L+1只袜子,在这其中选择两只,方案总数为C_{R-L+1}^2。(都在刷国家集训队的题目了,你应该知道组合数吧….

所以P(L,R,i)=n_i*(n_i-1)/2 C_{R-L+1}^2 .

答案如前所述,为\sum_{i=1} ^{n} P(q.l,q.r,i)

怎么优化

1.分块。

如果直接对每个询问区间暴力维护n_iO(m* k n)级别的复杂度很显然过不了。(k是一个常数。其实我不太会分析复杂度所以欢迎dalao指正

以样例为例,(话说这个样例不会被敏感词拦截吗)

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

样例图解

我们发现一些询问都和其它某(几)个询问有重叠部分。那其实,我们可以把有重叠部分的询问分组,先处理每组的第一个询问,然后处理与上一个询问不同的部分。

于是我们可以先按照左端点的大小排序,然后把排序后的队列分成几个小块(一般大小取\sqrt{m})。然后再在每个块内以右端点大小排序。我们就可以以块为单位处理。

虽然左端点的单调性在第二次排序的时候打乱了,但是第一次排序保证了同一个块内相邻两个左端点的变化在\sqrt{n}内。第二排序可以保证右端点只有加操作,没有减操作。

2.统计

前面有些大佬提到了维护平方和的办法。但是其实我认为有更好的办法(每次修改三行代码变为一行)。
进入每一个块内处理的时候,我们先暴力求出第一组询问的区间内,每个袜子的个数,存在数组num里。然后在前一个询问的基础上,对num修改。
根据前面的推导,对每个询问q,我们要求的是

\sum_{i=1}^{n}P(q.l,q.r,i)=num_i*(num_i-1)/2 C_{q.r-q.l+1}^2 .

(C右上角的2不是平方的意思…)

可以看出,同一个询问的分母都是确定的。所以我们现在关心如何通过修改num来快速得到分子。

重点来了,假设原来的num_i=x

假如我们要对num_i执行增加1的操作,那么实际上跟i有关的那一部分的分子的变化为:
增加后-增加前=(x+1)x-x(x-1)=2x.所以我们直接加上原来x的两倍即可。

假如我们要对num_i执行减小1的操作,那么实际上i这一部分分子的变化为:

减少后-减少前= (x-1)(x-2)-x(x-1)=-2(x-1),所以我们直接减去减少后的num_i的两倍即可。

于是以前的更改代码为:(以增加为例)

{

    tot-=num[i]* num[i];
    num[i]++;
    tot+=num[i]* num[i]; 
}

现在只需要:

{
    tot+=2* num[i]++;
}

但是….分母不是还有一个2么,直接约分不就行了…

于是乘以2可以直接省略,得到:

{
    tot+=num[i]++;
}

不开O2 363ms

开O2 191ms

细节见代码:

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using std::sort;
const int maxn=50000;
struct que
{
    int l,r,id;
}q[maxn+5];
struct blk
{
    int l,r;
}b[333];
int col[maxn+5],num[maxn+5],ans1[maxn+5],ans2[maxn+5],c[maxn+5][3];
//依次保存 颜色,上文中的num数组,分子,分母,组合数
int n,m,bs,bn,tot;
//bs为每个块的大小 bn为块的个数
//排序后可以一边分块一边计算
inline void read(int &x){//快读
    x=0;
    char c;
    do{
        c=getchar();
    }
    while(c<'0'||c>'9');
    do{
        x=x*10+c-'0';
        c=getchar();
    }
    while(c>='0'&&c<='9');
}
inline int min(int a,int b){
    return a<b?a:b;
}
inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
inline bool cmpl(que a,que b){//以l排序
    return a.l<b.l;
}
inline bool cmpr(que a,que b){//以r排序
    return a.r<b.r;
}
inline void pre(){//计算组合数
    c[1][0]=c[1][1]=1;
    for(register int i=2,j;i<=n;++i){
        c[i][0]=1;
        for(j=1;j<=2;++j){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
    }
}
int main(){
    read(n);
    read(m);
    pre();
    for(register int i=1;i<=n;++i){
        read(col[i]);
    }
    for(register int i=1;i<=m;++i){
        read(q[i].l);
        read(q[i].r);
        q[i].id=i;
    }
    bs=sqrt(m);
    sort(q+1,q+1+m,cmpl);
    //整体按l排序,保证每个块内左端点的变化不会太大
    for(register int i=1,g;i<=m;i+=bs){
    //i为每个块的左边界
        b[++bn].l=i;
        b[bn].r=min(i+bs-1,m);
        sort(q+i,q+b[bn].r+1,cmpr);//块内按右端点排序 以免右边反复无用增减                    
        memset(num,0,sizeof(num));
        tot=0;//分子
        //先处理这个块里的第一个询问
        for(register int j=q[b[bn].l].l;j<=q[b[bn].l].r;++j){
            tot+=num[col[j]]++;
        }
        ans1[q[b[bn].l].id]=tot;
        ans2[q[b[bn].l].id]=c[q[b[bn].l].r-q[b[bn].l].l+1][2];
        //分母无需再乘以二,因为分子计算的时候省略了二
        if(ans1[q[b[bn].l].id]==0)ans2[q[b[bn].l].id]=1;
        else {
                g=gcd(tot,ans2[q[b[bn].l].id]);
                ans1[q[b[bn].l].id]/=g;
                ans2[q[b[bn].l].id]/=g;
         }

         //在前面的基础上,处理块内其他询问
        for(register int k,j=b[bn].l+1;j<=b[bn].r;++j){
             if(q[j-1].l<q[j].l){//处理这一次询问少了的部分(复原)
                 for(k=q[j-1].l;k<q[j].l;++k){
                    tot-=--num[col[k]];
                    //注意运算符在前(根据推导,这里使用减少后的值)
                 }
             }
             else {
                for(k=q[j].l;k<q[j-1].l;++k){//处理这一次询问多出来的部分
                    tot+=num[col[k]]++;
                    //注意运算符在后(根据推导,这里使用增加前的值)
                }
             }

             for(k=q[j-1].r+1;k<=q[j].r;++k){//处理这个询问后面多出来的部分
                tot+=num[col[k]]++;
             }
             ans1[q[j].id]=tot;
             ans2[q[j].id]=c[q[j].r-q[j].l+1][2];
             if(ans1[q[j].id]==0)ans2[q[j].id]=1;
             else {
                g=gcd(tot,ans2[q[j].id]);
                ans1[q[j].id]/=g;
                ans2[q[j].id]/=g;
             }
        }
    }
    for(register int i=1;i<=m;++i){
        printf("%d/%d\n",ans1[i],ans2[i]);
    }
    // system("pause");
    return 0;
}

祝AC..

数列分块心得

//作者过弱, 此文过水, 不建议阅读

关于标记的用法

例如,在动态维护区间和的时候(虽然很多时候用线段树或者树状数组更方便),假如每块有3个属性:add,l,rlr标记了它的左端点和右端点,但add有两种用法:

1.在查询整体和的时候使用。(李煜东的书给出的就是这种)

当要使第i块每个元素都增加c时,执行add[i]+=c,然后逐一更新该块中每一项的值a[j] ,使其增加c。//O(1)O(n)

当要查询时,如果查询该块的某部分,则逐一累加那一部分的元素然后返回;如果查询整体的和,就直接返回原始处理的sum加上add[i]*len[i]。//O(n)O(1)

2.查询部分元素的时候使用。

当要使第i块每个元素都增加c时,执行add[i]+=c,然后把sum[i]加上len[i]*c;//O(1)O(1)

当要查询时,如果查询该块的某部分,则逐一累加那一部分,然后加上add[i]*(这一部分的长度);如果查询整体的和,直接返回sum[i];//O(n)O(1)

第二种方法可以在修改的时候省掉一个O(n)

关于每块元素的个数

方法不同的话,长度为n的数列每一块的元素个数不一定是\sqrt{n},也不一定小于它。可能大于它。

例如,如果以李煜东书上的分块方法,给24个元素的数列分块,每一块的元素个数分别为:4,4,4,4,8。(就因为这个原因一道题卡了很久。不过他这种方法应该是错的吧…)