2016大连online contest总结

icpc online_contest

首先，给出叉姐的题解链接

1001 Different Circle Permutation

1002 Different GCD Subarray Query

啰嗦

这题是我一开始就看的题目，第一眼感觉就是预处理有效的gcd段后离线处理。固定一个端点i(左和右都可以，假设是右端点)，随着另外一个端点j的变换，[j,i]的gcd最多只有logN个不同的值。由于我们的询问求的是区间内不同的子区间的gcd值有多少个，所以对于固定右端点i的区间，如果gcd值相同，只保留最短的那一个(下称为有效区间)，长的不需要保留。

于是问题就转化为Q个询问区间中，包含了多少个NlogN个有效区间，而且gcd值不同。对于段包含段的问题，经典的解法就是离线。

我们将询问和有效的gcd段按照右端点排序后，那么对于每个询问[xi,yi]，所有右端点<=yi的在排序后的这个区间的前面。所以前面的段只要满足左端点>=xi。所以，对于纯的区间包含区间问题，按照右端点从小到大枚举，遇到一个有效区间在其左端点处+1，遇到一个询问区间，询问其左端点右边的和，就是该询问的结果。上述的+1和求和问题，可以用树状数组解决。

然而这个问题求的是不同gcd的个数，所以对于区间内相同的gcd，我们只能算一次。由于我们按照右端点的顺序做的时候，只需要统计询问区间的左端点的右边的不同左端点的gcd的个数，所以对于gcd相同的区间，只需要记下左端点最靠右的那一个就可以了。

总结

1.这题我一开始的写法是用了个ST表和跳表预处理有效区间，sort之后再做。这一部分写的特别蠢，编程复杂度、时间复杂度、空间复杂度都比较大。后来向敦爷学习之后，知道可以直接把以i为右端点的有效区间开个数组存起来(大小最多为logN)，求以i+1为右端点的时候扫一遍更新gcd，并合并gcd相同的就可以了。不需要预处理，好些很多。

2.对于询问区间的离线，可以sort，也可以用vector。用vector方便很多，虽然STL库常数很大，但是由于是O(N)的，而sort是O(N*logN)的，所以实际上两个效率差不多，建议用vector。

代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
const int maxn=100000+100;
int N,Q,L[maxn];        // L[i]表示第i个询问区间的左端点
int A[maxn],Ans[maxn];  // A[]原数组，Ans[]纪录询问区间的答案
int G[1000*1000+100];   //G[i]用于纪录gcd值为i左端点最靠右的位置
vector <int> ope[maxn]; // 离线，记下询问
int Tree[maxn];   // 树状数组求和
int gcd(int a,int b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
void add(int i,int x)
{
    for (; i<=N; i+=(i&(-i))) Tree[i]+=x;
}
int que(int i)
{
    int ret=0;
    for (; i; i-=(i&(-i))) ret+=Tree[i];
    return ret;
}
void Done()
{
    static int o[50][2];   // o数组纪录不同的gcd值以及靠右的左端点
    int maxf=0;
    For(i,1,N) maxf=max(maxf,A[i]);
    memset(G,0,sizeof(int)*(maxf+2)); // 初始化G
    int m=0;   // m统计o数组的个数
    memset(Tree,0,sizeof(int)*(N+2)); // 初始化树状数组
    For(i,1,N)
    {
        For(j,1,m) o[j][0]=gcd(o[j][0],A[i]); // 更新有效gcd值
        o[++m][0]=A[i];   // 添加区间[i,i]的gcd值
        o[m][1]=i;        // 纪录左端点
        int mm=1;
        For(j,2,m)       // 接下来是合并相同gcd值
            if (o[j][0]!=o[mm][0])
            {
                o[++mm][0]=o[j][0];
                o[mm][1]=o[j][1];
            }
            else o[mm][1]=o[j][1];
        m=mm;
        For(j,1,m)
            if (G[o[j][0]] < o[j][1]) // 判断新的有效区间的左端点是否更新了相同gcd的靠右左端点
            {
                add(N-G[o[j][0]]+1,-1); // 删除上一个靠右左端点
                add(N-o[j][1]+1,1);    // 添加新的靠右左端点
                G[o[j][0]]=o[j][1];    // 更新靠右左端点
            }
        For(j,0,ope[i].size()-1)  //统计右端点为i的询问区间的答案
        {
            Ans[ope[i][j]]=que(N-L[ope[i][j]]+1);
        }
    }
}
int main()
{
    for (; scanf("%d%d",&N,&Q)!=EOF; )
    {
        For(i,1,N) ope[i].clear();   // 初始化
        For(i,1,N) scanf("%d",&A[i]);
        For(i,1,Q)
        {
            int x,y; scanf("%d%d",&x,&y);
            ope[y].push_back(i);    // 按右端点离散化，右端点y有一个询问，是第i个询问
            L[i]=x; // 纪录询问i的左端点
        }
        Done();
        For(i,1,Q) printf("%d\n",Ans[i]); // 输出Q个询问的答案
    }
    return 0;
}