hdu5212 Code 莫隊算法
來源：程序員人生 發布時間：2015-05-19 08:09:14 閱讀次數：3171次
這道題需要1些莫隊算法的知識
定義記號f(A,B)表示詢問區間A，B時的答案
用記號＋表示集合的并
利用莫隊算法我們可以計算出任意f(A,A)的值
無妨假定A=[l1,r1],B=[l2,r2],C=[r1+1,l2?1]
容易知道f(A,B)=f(A+B+C,A+B+C)+f(C,C)?f(A+C,A+C)?f(C+B,C+B)
因此1個詢問被拆成4個可以用莫隊算法做的詢問
總的時間復雜度為O(msqrt(n))
(以上是官方題解)
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int N = 30000*4 + 10;
int pos[N];
struct pp{
int l,r,id;
int ans;
}p[N];
int cmp(pp a,pp b){
if(pos[a.l]==pos[b.l]) return a.r < b.r;
return a.l < b.l;
}
int cmp2(pp a,pp b){
return a.id < b.id;
}
struct que{
int l1,l2,r1,r2;
}q[N];
int block,n,k,m,num;
int a[N],cnt[N],answer;
LL x;
map<LL,int> mm;
void update(int x,int v){
int val = k - a[x];
if(val <= 0) return ;
answer += cnt[val]*v;
cnt[a[x]] += v;
}
void solve(){
int l,r;
answer = 0;
for(int i=1,l=1,r=0;i<=num;i++){//按塊進行更新
for(;r<p[i].r;r++)
update(r+1,1);
for(;r>p[i].r;r--)
update(r,⑴);
for(;l<p[i].l;l++)
update(l,⑴);
for(;l>p[i].l;l--)
update(l⑴,1);
p[i].ans = answer;
}
}
int main(){
while(scanf("%d",&n)!=EOF){
mm.clear();
num = 0;
block = (int)sqrt(n)+1;
for(int i=1;i<=n;i++) pos[i] = i/block + 1;
scanf("%d",&k);
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l1,l2,r1,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
q[i].l1 = l1 , q[i].r1 = r1 , q[i].l2 = l2 , q[i].r2 = r2;
p[++num].l = l1 , p[num].r = l2⑴ ;
x = l1*40000+(l2⑴);
mm[x] = num;
p[num].id = num;
p[++num].l = r1+1 , p[num].r = r2 ;
x = (r1+1)*40000+r2;
mm[x] = num;
p[num].id = num;
if(l2⑴ >= r1+1){
p[++num].l = r1+1 , p[num].r = l2⑴ ;
x = (r1+1)*40000+(l2⑴);
mm[x] = num;
p[num].id = num;
}
p[++num].l = l1 , p[num].r = r2 ;
x = l1*40000+r2;
mm[x] = num;
p[num].id = num;
}
sort(p+1,p+1+num,cmp);
solve();
sort(p+1,p+1+num,cmp2);
for(int i=1;i<=m;i++){
int l1,l2,r1,r2;
l1 = q[i].l1 , l2 = q[i].l2 , r1 = q[i].r1 , r2 = q[i].r2 ;
LL ans = 0;
x = l1*40000+r2;
ans += p[mm[x]].ans;
if(l2⑴>=r1+1){
x = (r1+1)*40000+(l2⑴);
ans += p[mm[x]].ans;
}
x = (r1+1)*40000+r2;
ans -= p[mm[x]].ans;
x = l1*40000+(l2⑴);
ans -= p[mm[x]].ans;
printf("%lld
",ans);
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
