学习了一下莫队,本质十分简单,就是给询问安排一定顺序,离线处理,按相邻的两个询问区间来拨动L,R指针,可以令拨动次数至多为 sqrt(N)*N次 ,排序可以结合分块使用sort。
此题题意:给出N个数,M个询问,对于每个询问,有一组[L,R],输出这个区间内所有子区间的GCD的和。
范围:T<=3,N,M<=10000
解法: (1)预处理+暴力 时间复杂度为 (N*log(N*N)+N*M) 900ms
(2)预处理+莫队 时间复杂度为 (N*log(N*N)+N*sqrt(N)*log(N)) 姿势比较丑,用了很多STL库里的东东简化编写,600ms
思路:可以发现,对于每个数的,如果其作为一个区间的右端点,那么其往左所有的子区间,至多有logN个不同的数。(因为越往左,数越小,每小一次要丢一个质因数,至多logN个质因数。)
可以对其进行预处理,得到每个数以及其(left,right),left表示以这个数作为gcd的左端点的最左端,同理right最右端。
预处理方法,建一个b[i] 数组,表示此时以 R 作为右端点,i作为左端点时的gcd,R每往有推一个,暴力往左求gcd,直到新得到的gcd和原来的b[i]相等为止(因为再往左都一样啦)。有了这个数组,就可以很方便得到logN个不同的数以及其left,right。由于每个数至多减小logN次,求解gcd复杂度是logN,所以预处理的复杂度是log(n*n)*n 。
同理求出左端点的logN个不同的阶段数,就可以作为莫队算法时的转移啦,由于转移需要处理logN个不同的阶段,来得到 [L,R] 固定一端的gcd和,所以转移复杂度是logN,故而整的复杂度是O(N*log(N*N)+N*sqrt(N)*log(N)) 。
代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<iostream>
#include<stdlib.h>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<bitset>
#pragma comment(linker, "/STACK:1024000000,1024000000")
template <class T>
bool scanff(T &ret){ //Faster Input
char c; int sgn; T bit=0.1;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
if(c==' '||c=='\n'){ ret*=sgn; return 1; }
while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
ret*=sgn;
return 1;
}
#define inf 1073741823
#define llinf 4611686018427387903LL
#define PI acos(-1.0)
#define lth (th<<1)
#define rth (th<<1|1)
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define drep(i,a,b) for(ll i=a;i>=b;i--)
#define gson(i,root) for(ll i=ptx[root];~i;i=ed[i].next)
#define tdata int testnum;scanff(testnum);for(int cas=1;cas<=testnum;cas++)
#define mem(x,val) memset(x,val,sizeof(x))
#define mkp(a,b) make_pair(a,b)
#define findx(x) lower_bound(b+1,b+1+bn,x)-b
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
const int NN=10010;
ll n,m,a[NN],b[NN],ans[NN],sum,l,r,belong[NN];
struct node{
ll l,r,idx;
}q[NN];
bool cmp(node x,node y){
if(belong[x.l]==belong[y.l])return x.r<y.r;
else return x.l<y.l;
}
struct node2{
ll val,l,r;
node2(ll vv,ll lx,ll rx):val(vv),l(lx),r(rx){}
};
vector<node2> lx[NN];
vector<node2> rx[NN];
set<ll> st;
set<ll> :: iterator it;
bool cmp2(ll x,ll y){return x>y;}
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
void init(){
mem(b,0);
rep(i,1,n){
b[i]=a[i];
st.clear();st.insert(a[i]);
drep(j,i-1,1){
ll t=gcd(b[j],b[j+1]);
if(t==b[j])break;
b[j]=t;
st.insert(t);
}
if(i>1)rep(j,0,ll(rx[i-1].size())-1)st.insert(rx[i-1][j].val);
rx[i].clear();
for(it=st.begin();it!=st.end();it++){
ll vo=*it;
ll lo=lower_bound(b+1,b+1+i,vo)-b;
ll ro=upper_bound(b+1,b+1+i,vo)-b-1;
if(b[lo]==vo&&b[ro]==vo)
rx[i].pb(node2(vo,lo,ro));
}
}
mem(b,0);
drep(i,n,1){
b[i]=a[i];
st.clear();st.insert(a[i]);
rep(j,i+1,n){
ll t=gcd(b[j],b[j-1]);
if(t==b[j])break;
b[j]=t;
st.insert(t);
}
if(i<n)rep(j,0,ll(lx[i+1].size())-1)st.insert(lx[i+1][j].val);
lx[i].clear();
for(it=st.begin();it!=st.end();it++){
ll vo=*it;
ll lo=lower_bound(b+i,b+1+n,vo,cmp2)-b;
ll ro=upper_bound(b+i,b+1+n,vo,cmp2)-b-1;
if(b[lo]==vo&&b[ro]==vo)
lx[i].pb(node2(vo,lo,ro));
}
}
}
void updater(ll pos,ll add){
ll sz=rx[pos].size();
rep(i,0,sz-1){
if(l<rx[pos][i].l)
sum+=add*rx[pos][i].val*(rx[pos][i].r-rx[pos][i].l+1);
if(l>=rx[pos][i].l&&l<=rx[pos][i].r)
sum+=add*rx[pos][i].val*(rx[pos][i].r-l+1);
}
}
void updatel(ll pos,ll add){
ll sz=lx[pos].size();
rep(i,0,sz-1){
if(r>lx[pos][i].r)
sum+=add*lx[pos][i].val*(lx[pos][i].r-lx[pos][i].l+1);
if(r>=lx[pos][i].l&&r<=lx[pos][i].r)
sum+=add*lx[pos][i].val*(r-lx[pos][i].l+1);
}
}
void solve(){
l=1,r=0;sum=0;
rep(i,1,m){
for(;r<q[i].r;r++)updater(r+1,1);
for(;r>q[i].r;r--)updater(r,-1);
for(;l<q[i].l;l++)updatel(l,-1);
for(;l>q[i].l;l--)updatel(l-1,1);
ans[q[i].idx]=sum;
}
rep(i,1,m)printf("%lld\n",ans[i]);
}
main(){
tdata{
scanff(n);
rep(i,1,n)scanff(a[i]);
scanff(m);
rep(i,1,m){
scanff(q[i].l);
scanff(q[i].r);
q[i].idx=i;
}
sort(q+1,q+1+m,cmp);
ll block=sqrt(n);
rep(i,1,n)belong[i]=((i-1)/block)+1;
init();
solve();
}
}
版权声明:本文为GrassTreeFlower原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。