HDU 5869 Different GCD Subarray Query
线段树,离线
题目
长度n的序列, m个询问区间[L, R], 问区间内的所有子段的不同GCD值有多少种。
思路
区间gcd收敛非常快,首先暴力处理所有区间gcd及位置,复杂度nlogA。
%%%
for(int i=1;i<=n;i++)
{
int cur=num[i], pos=i;
for(int j=0;j<gg[i-1].size();j++)
{
int nowgcd=mygcd(cur, gg[i-1][j].first);
if(nowgcd!=cur)
{
gg[i].push_back(make_pair(cur, pos));
cur=nowgcd;
pos=gg[i-1][j].second;
}
}
gg[i].push_back(make_pair(cur, pos));
}
然后离线询问,按右端点排序。用一个pos数组记录每个gcd最后出现的位置。注意,这个数组更新是有条件的,必须有一个同样的gcd,出现的更晚,才能更新。因为我们的右端点是只增不减的,所以晚出现的gcd可以代替早出现的,而早出现的不能代替晚出现的。(l变化就可能导致先出现的gcd被漏出去)
线段树维护某一个位置,出现了多少不同的gcd。所以在某位置加入一个新的gcd时就在那个位置加一,扣掉一个gcd就减一。单点更新区间查询。
支持修改的话,参考线段树二分,不过要多几个log。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=100007;
const int MAXNUM=10*MAXN;
//gcd
int num[MAXN], gcdlapos[MAXNUM];;
int mygcd(int a, int b) { return b==0 ? a : mygcd(b, a%b); }
vector<pair<int, int>> gg[MAXN];
//询问
struct Query
{
int l, r, ans, ne;
void rd() { scanf("%d%d", &l, &r);ans=0; }
}q[MAXN];
int qhead[MAXN];
//线段树
int stree[MAXN<<2];
inline void pushup(int rt) { stree[rt]=stree[rt<<1]+stree[rt<<1|1]; }
void build() { M(stree, 0); }
void update(int pos, int v, int l, int r, int rt)
{
if(l==r) { stree[rt]+=v;return; }
int mid=(l+r)>>1;
if(pos<=mid) update(pos, v, lson);
else update(pos, v, rson);
pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
if(L<=l&&r<=R) return stree[rt];
int mid=(l+r)>>1;
int res=0;
if(L<=mid) res+=query(L, R, lson);
if(mid<R) res+=query(L, R, rson);
return res;
}
int main()
{
int n, m;
while(scanf("%d%d", &n, &m)==2)
{
for(int i=1;i<=n;i++) scanf("%d", &num[i]), gg[i].clear();
M(qhead, -1);
for(int i=1;i<=m;i++)
{
q[i].rd();
q[i].ne=qhead[q[i].r];
qhead[q[i].r]=i;
}
for(int i=1;i<=n;i++)
{
int cur=num[i], pos=i;
for(int j=0;j<gg[i-1].size();j++)
{
int nowgcd=mygcd(cur, gg[i-1][j].first);
if(nowgcd!=cur)
{
gg[i].push_back(make_pair(cur, pos));
cur=nowgcd;
pos=gg[i-1][j].second;
}
}
gg[i].push_back(make_pair(cur, pos));
}
build();
M(gcdlapos, 0);
int curr=0;
for(int i=1;i<=n;i++)
{
for(auto tmp:gg[i])
{
int curgcd=tmp.first;
int curpos=tmp.second;
if(curpos>gcdlapos[curgcd])//这个判断不能丢
{
if(gcdlapos[curgcd])
update(gcdlapos[curgcd], -1, 1, n, 1);
update(curpos, 1, 1, n, 1);
gcdlapos[curgcd]=curpos;
}
}
for(int j=qhead[i];~j;j=q[j].ne)
{
q[j].ans=query(q[j].l, q[j].r, 1, n, 1);
}
}
for(int i=1;i<=m;i++)
{
printf("%d\n", q[i].ans);
}
}
return 0;
}