HDU5213
给你一个n个数的序列a，给你q个询问，每次询问给两个不相交的区间，求a[i]+a[j]=k的方案数
i属于第一个区间，j属于第二个区间。
对于这种两个区间内查询得问题，我们要看看能不能转化为一个区间之内的查询操作。
我们设f(l,r)f(l,r)为[l,r][l,r]区间内选i,j，a[i]+a[j]=ka[i]+a[j]=k的方案数。若两个区间为(l1,r1),(l2,r2)(l1,r1),(l2,r2)
则答案为f(l1,r2)?f(l1,l2)?f(r1,r2)+f(r1,l2)f(l1,r2)?f(l1,l2)?f(r1,r2)+f(r1,l2)
所以我们对这四个部分分别处理就可以了。这就是多区间询问转为莫队算法的一种套路。
代码
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
int a[maxn];
int pos[maxn];
ll sum[maxn];
ll ans[maxn];
int n,m,k;
struct data
{int l,r,id,belong;//belong是这个查询属于哪个查询，id是这个查询对答案贡献是+还是-。
}Q[maxn];
bool cmp(const data &a,const data &b)
{if(pos[a.l]==pos[b.l]) return a.r<b.r;return pos[a.l]<pos[b.l];
}
int L=0,R=0;
ll Ans=0;
void add(int x)
{if(k>a[x]&&k-a[x]<n) Ans+=sum[k-a[x]];sum[a[x]]++;
}
void del(int x)
{sum[a[x]]--;if(k>a[x]&&k-a[x]<n) Ans-=sum[k-a[x]];
}
int main()
{while(scanf("%d%d",&n,&k)!=EOF){L=0,R=0,Ans=0;for(int i=1;i<=n;i++) sum[i]=0;int sz=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[i]=i/sz;}scanf("%d",&m);for(int i=1;i<=m;i++) ans[i]=0;int cnt=1;for(int i=1;i<=m;i++){int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);Q[cnt].l=l1,Q[cnt].r=r2,Q[cnt].id=1,Q[cnt++].belong=i;Q[cnt].l=l1,Q[cnt].r=l2-1,Q[cnt].id=-1,Q[cnt++].belong=i;Q[cnt].l=r1+1,Q[cnt].r=r2,Q[cnt].id=-1,Q[cnt++].belong=i;Q[cnt].l=r1+1,Q[cnt].r=l2-1,Q[cnt].id=1,Q[cnt++].belong=i;}cnt--;sort(Q+1,Q+1+cnt,cmp);for(int i=1;i<=cnt;i++){while(R<Q[i].r){R++;add(R);}while(L>Q[i].l){L--;add(L);}while(L<Q[i].l){del(L);L++;}while(R>Q[i].r){del(R);R--;}ans[Q[i].belong]+=1LL*Ans*Q[i].id;}for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);}return 0;
}