hdu 5930 GCD ( 区间gcd的种类 线段树 )
2016-11-23 本文已影响41人
Out_Of_Cage
题目大意
给出n个数，q次询问，每次修改其中一个数，并询问这n个数组成的所有子区间的gcd的种类。
解答
gcd的种类最多不超过nlogC(C是数的最大值)个，我们可以全部存起来，并存下每种gcd有多少个子区间可以构成。枚举区间左端点，找logC个gcd变化的右端点并计算种类和个数，把结果用map存一下。
每次单点修改，修改的只是包含x的区间，分别以x为区间左端点和区间右端点，可以求出两个不超过logC的gcd以及对应区间集合，暴力合并一下是O((logC)2)，加上修改map的时间复杂度是O((logC)2×log(n*logC))。
关于求gcd的logC个的变化位置，我的做法是用线段树。以x为左端点为例，线段树查找[x,N]的gcd变化位置，首先第一个变化位置就是x本身，gcd值为A[x]自己，把gcd值传进递归函数里(记为gcdv)，假设[le,ri]⊆[x,N]，那么如果[le,ri]的gcd和gcdv构成的gcd不等于gcdv(可以用倍数关系判断)，那么[le,ri]必然存在一个gcd变化位置，需要递归下去。 主要代码如下：
int query_right(int w,int le,int ri,int &x,int &y,int v[],int pos[],int &cnt,int gcdv)
{ // gcdv传进的是[x,le-1]区间的gcd值，函数返回值是gcd值
int mid=(le+ri)>>1;
if (x<=le && ri<=y)
{
if (Tree[w] % gcdv==0) return gcdv; // 若Tree[w]是gcdv倍数，gcd不变化
if (le==ri) // 如果是一个点，正好是变化点
{
gcdv=gcd(gcdv,Tree[w]);
cnt++;
v[cnt]=gcdv;
pos[cnt]=le;
return gcdv;
}
if (Tree[w<<1]%gcdv!=0)
gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
if (Tree[w<<1|1]%gcdv!=0)
gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
return gcdv;
}
if (mid>=x)
gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
if (mid+1<=y)
gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
return gcdv;
}
上面是固定x为左端点的代码，固定x为右端点的代码类似。
求变化点也可以二分加线段树，不过可能会TLE。
这样做，求变化点的时间复杂度是O(logn×logC+logC×logC)。
暴力合并左边和右边的区间的时间复杂度是O((logC×logC×log(n*logC))。不过数据很难达到logC个变化点，因此三个log的时间复杂度过这题效率也非常高。
如果要追求两个log的效率，可以先把左边和右边的区间合并起来，合并后不同的gcd也同样是logC个，然后再去更新map的值。（合并可以新开一个map，不过感觉没有什么必要）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#define bll long long
#define dou double
#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--)
#define rep(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define rek(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))
//__builtin_popcountll
using std::sort;
using std::max;
using std::min;
using std::swap;
const int maxn=50000+10;
int N,Q,A[maxn],Tree[maxn*4];
std::map <int,bll> Map; // 统计不同种类的gcd，并且记录每个gcd各有多少个
int gcd(int a,int b)
{
while(b)
{
int c=a%b;
a=b,b=c;
}
return a;
}
void maketree(int w,int le,int ri) // 初始化构树
{
if (le==ri)
{
Tree[w]=A[le];
return ;
}
int mid=(le+ri)>>1;
maketree(w<<1,le,mid);
maketree(w<<1|1,mid+1,ri);
Tree[w]=gcd(Tree[w<<1],Tree[w<<1|1]);
}
void modify(int w,int le,int ri,int &x,int &v) // 单点修改
{
if (le>x || ri<x) return ;
if (le==ri)
{
Tree[w]=v;
return ;
}
int mid=(le+ri)>>1;
modify(w<<1,le,mid,x,v);
modify(w<<1|1,mid+1,ri,x,v);
Tree[w]=gcd(Tree[w<<1],Tree[w<<1|1]);
}
int query_right(int w,int le,int ri,int &x,int &y,int v[],int pos[],int &cnt,int gcdv)
{ // gcdv传进的是[x,le-1]区间的gcd值，函数返回值是gcd值
int mid=(le+ri)>>1;
if (x<=le && ri<=y)
{
if (Tree[w] % gcdv==0) return gcdv; // 若Tree[w]是gcdv倍数，gcd不变化
if (le==ri) // 如果是一个点，正好是变化点
{
gcdv=gcd(gcdv,Tree[w]);
cnt++;
v[cnt]=gcdv;
pos[cnt]=le;
return gcdv;
}
if (Tree[w<<1]%gcdv!=0)
gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
if (Tree[w<<1|1]%gcdv!=0)
gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
return gcdv;
}
if (mid>=x)
gcdv=query_right(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
if (mid+1<=y)
gcdv=query_right(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
return gcdv;
}
int query_left(int w,int le,int ri,int &x,int &y,int v[],int pos[],int &cnt,int gcdv)
{ // 求区间gcd，并且记下每个gcd第一次改变的位置(左边)
int mid=(le+ri)>>1;
if (x<=le && ri<=y)
{
if (Tree[w] % gcdv==0) return gcdv;
if (le==ri)
{
gcdv=gcd(gcdv,Tree[w]);
cnt++;
v[cnt]=gcdv;
pos[cnt]=le;
return gcdv;
}
if (Tree[w<<1|1]%gcdv!=0)
gcdv=query_left(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
if (Tree[w<<1]%gcdv!=0)
gcdv=query_left(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
return gcdv;
}
if (mid+1<=y)
gcdv=query_left(w<<1|1,mid+1,ri,x,y,v,pos,cnt,gcdv);
if (mid>=x)
gcdv=query_left(w<<1,le,mid,x,y,v,pos,cnt,gcdv);
return gcdv;
}
void get_right(int w,int v[],int pos[],int &cnt) // 得到左端点为w，右端点为w-N的gcd改变位置
{
v[cnt=1]=A[w];
pos[cnt]=w;
int gcdv=A[w];
query_right(1,1,N,w,N,v,pos,cnt,gcdv);
pos[cnt+1]=N+1;
}
void get_left(int w,int v[],int pos[],int &cnt) // 得到右端点w，左端点为1-w的gcd改变位置
{
v[cnt=1]=A[w];
pos[cnt]=w;
int gcdv=A[w];
int x=1;
query_left(1,1,N,x,w,v,pos,cnt,gcdv);
pos[cnt+1]=0;
}
void add(int gcdv,bll gcdnum) // 修改Map
{
Map[gcdv]+=gcdnum;
if (Map[gcdv]==0) Map.erase(gcdv);
}
void Prepare() // 初始化
{
static int cnt,v[50],pos[50];
maketree(1,1,N);
Map.clear();
For(i,1,N)
{
get_right(i,v,pos,cnt);
For(j,1,cnt)
add(v[j],pos[j+1]-pos[j]);
}
}
void solve(int v[2][50],int p[2][50],int cnt[2],int d) // 合并两边的区间gcd，并更新
{
For(i,1,cnt[0])
For(j,1,cnt[1])
{
int gcdv=gcd(v[0][i],v[1][j]);
long long g=(bll)abs(p[0][i]-p[0][i+1])*abs(p[1][j]-p[1][j+1]);
add(gcdv,g*d);
}
}
void printt() // 打印信息，用于调试
{
std::map<int,bll> :: iterator it;
for (it=Map.begin(); it!=Map.end(); it++)
printf("%d %lld\n",it->first,it->second);
printf("---\n");
}
int Done(int x,int rr) // 修改询问操作
{
static int cnt[2],v[2][50],p[2][50];
get_left(x,v[0],p[0],cnt[0]);
get_right(x,v[1],p[1],cnt[1]);
solve(v,p,cnt,-1);
A[x]=rr;
modify(1,1,N,x,rr);
get_left(x,v[0],p[0],cnt[0]);
get_right(x,v[1],p[1],cnt[1]);
solve(v,p,cnt,1);
return (int)Map.size(); // Map的大小就是gcd的种类个数
}
int main(int argc, char* argv[])
{
int zz=0;
scanf("%d",&zz);
For(test,1,zz)
{
printf("Case #%d:\n",test);
scanf("%d%d",&N,&Q);
For(i,1,N) scanf("%d",&A[i]);
Prepare();
For(i,1,Q)
{
int x,p; scanf("%d%d",&x,&p);
int ans=Done(x,p);
printf("%d\n",ans);
}
}
return 0;
}
