E - No Pain No Game 线段树 离线处理 区间排序

E - No Pain No Game

 HDU - 4630

这个题目很好,以后可以再写写。
这个题目就是线段树的离线写法,推荐一个博客:https://blog.csdn.net/u010033217/article/details/38156507
这个题目因为数据太大,所以如果直接每一个查询都直接查肯定会T的,所以就要用到线段树。
我直接说思路吧,
第一步,预处理所有可能的数据,就是把每一个数的因子全部求出来,用一个数组存下来。这里就要用到调和级数,用n*logn的复杂度预处理出1~n的所有数的约数。
第二步,输入数据,对于要查询的数据用结构体处理,然后对于结构体的右端点进行排序,从小到大。//这个是为了第三步,第四步
第三步,对于给定的数列进行处理,每次处理一个数,如果这个数的因子前面出现过,那么就更新这个数前面这个位置的最大的gcd,然后再更新这个数字出现的新位置。
//这个是关键,更新这个新位置是必要的,这个可以自己想明白吧。为什么是更新前面的位置呢?因为更新前面的位置之后,第四步就判断到目前位置的最大值就可以直接判断了,还不懂可以看第四步解析。
第四步,每次处理完一个数,都要判断查询里面是不是存在这个。
//因为本来应该是区间更新,现在可以用单点更新代替,这个是因为排序之后的r会越来越大,所以你只要更新区间的左端点就可以了,左端点被包含了,右端点肯定被包含进去了。
最后一步输出答案。
 询问【L,R,max_gcd(x,y)】,区间内任意两个值的最大gcd。这样的话,如果每来一个查询我就处理的话那就很难降低复杂度,是采用离线处理的思想,我们首先将所有的查询全部读入,然后将查询按右端点排序(为什么按照右端点排序呢,前往下看)。   

      要求区间内任意两个点的gcd的最大值,对于这个问题,如果不做一些预处理,我们是不能有效的进行操作的,因为这个问题不是像区间极值哪些问题具有合并性的。所以我们要考虑gcd的特征,两个数的gcd一定是这两个数的因子,这样的话我们就能处理出每个数的因子,通过判断这两个数是否有公因子来更新答案(公因子比之前维护的ans大)。那么我们现在可以捋一捋所知信息:对于一个区间,我们能否通过某种方法查看这个区间内各个数字的因子,然后判断出最大的公因子即为所求。那么假设现在i位置的数字为a[i],那么如果a[i]具有因子x,如果某个位置a[j]也具有因子x,那么区间[i,j]至少拥有这样的gcd为x,如果x大于当前的ans,那么我们就可以更新答案了。    

      根据上述信息,我们维护一颗线段树,线段树维护的值是区间内最大的gcd。首先我们预处理所有数字的因子,然后我们将排序过后的区间从左到右依次处理(为了加强理解,设定k<i<j),每扫描一个值a[i],我们查看a[i]的所有因子,对于某一个因子x,如果之前有某个值a[k]也存在这样的因子x,那么就可以更新区间[k,i](这个非常关键),然后这个x也可能会更新后面的某个区间[i,j](假设a[j]包含因子x)。接着我们考虑数组pre[x]代表x这个因子上一次(最近一次)出现的位置(即某个数值包含因子x),如果没有出现过就标记为-,如果之前处理了所有的pre[x],那么我们枚举每个数值的因子,就可以根据pre数组判断能否更新区间[pre[x], now_postion],那么对于查询[l , r]只要它在[pre[x], now_postion]中,那么就可以更新线段树的值。那么对于按右端点排序好的查询,如果在不断update的过程中遇到了查询的右端点,那么我们就可以做查询即可。
———————————————— https://blog.csdn.net/u010033217/article/details/38156507

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 5e4 + ; int a[maxn], pre[maxn], n, m;
int ans[maxn];
vector<int>vec[maxn]; struct node
{
int l, r, id;
int Max;
}tree[maxn*];
node in[maxn]; void init()
{
for(int i=;i<maxn;i++)
{
for(int j=i;j<maxn;j+=i)
{
vec[j].push_back(i);
}
}
} bool cmp(node a,node b)
{
if (a.r == b.r) return a.l < b.l;
return a.r < b.r;
} void build(int id,int l,int r)
{
tree[id].l = l;
tree[id].r = r;
tree[id].Max = ;
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} void push_up(int id)
{
tree[id].Max = max(tree[id << ].Max, tree[id << | ].Max);
} void update(int pos,int val,int id)
{
tree[id].Max = max(tree[id].Max, val);
if(tree[id].l==tree[id].r)
{
tree[id].Max = max(tree[id].Max, val);
return;
}
int mid = (tree[id].l + tree[id].r) >> ;
if (pos <= mid) update(pos, val, id << );
else update(pos, val, id << | );
} int query(int l,int r,int id)
{
if(l<=tree[id].l&&r>=tree[id].r)
{
return tree[id].Max;
}
int ans = ;
int mid = (tree[id].l + tree[id].r) >> ;
if (l <= mid) ans = max(ans, query(l, r, id << ));
if (r > mid) ans = max(ans, query(l, r, id << | ));
return ans;
} int main()
{
int t;
init();
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
build(, , n);
scanf("%d", &m);
for(int i=;i<=m;i++)
{
scanf("%d%d", &in[i].l, &in[i].r);
in[i].id = i;
}
memset(pre, -, sizeof(pre));
sort(in + , in + + m, cmp);
for(int i=,j=;i<=n&&j<=m;i++)
{
for(int k=;k<vec[a[i]].size();k++)
{
int tmp = vec[a[i]][k];
if(pre[tmp]!=-)
{
update(pre[tmp], tmp, );
}
pre[tmp] = i;
}
while(in[j].r==i&&j<=m)
{ if(in[j].l==in[j].r)
{
ans[in[j].id] = ;
j++;
continue;
}
ans[in[j].id] = query(in[j].l, in[j].r, );
j++;
}
}
for(int i=;i<=m;i++)
{
printf("%d\n", ans[i]);
}
}
return ;
}
上一篇:Windows10 使用docker toolbox安装docker


下一篇:线段树+离线 hdu5654 xiaoxin and his watermelon candy