CF877F
题目大意：给定n个数有正有负，有Q次询问，每次询问区间[l,r]中有几个子区间满足和为k
做法：显然的莫队
每次用map记录一下当前区间[l,r]中的前缀和的值的个数
然后r的话找sum[r]-k的，l找sum[l]+k即可
不过是一道卡常题，不能用map要用unordered_map才能过
代码：
#pragma GCC optimize(3)
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define N 100005
#define ll long long
#include <tr1/unordered_map>
using namespace std;
int n,k,opt[N],Q;ll a[N],ans[N];
struct Node{int l,r,id;}q[N];
tr1::unordered_map<ll,ll> mp;
inline int gt(int x){return (x-1)/610+1;}
inline bool cmp(Node aa,Node bb){if (gt(aa.l)==gt(bb.l)) return aa.r<bb.r;else return gt(aa.l)<gt(bb.l);}
inline void solve(){
int l=1,r=0;ll ans1=0;mp[0]++;
for (int i=1;i<=Q;i++){
while (l>q[i].l){l--;ans1=ans1+mp[a[l-1]+k];mp[a[l-1]]++;}
while (r<q[i].r){r++;ans1=ans1+mp[a[r]-k];mp[a[r]]++;}
while (l<q[i].l){mp[a[l-1]]--;ans1=ans1-mp[a[l-1]+k];l++;}
while (r>q[i].r){mp[a[r]]--;ans1=ans1-mp[a[r]-k];r--;}
ans[q[i].id]=ans1;
}
}
inline int read(){
char ch;int f=1,w=0;
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) w=w*10+ch-'0';
return w*f;
}
int main(){
n=read();k=read();
for (int i=1;i<=n;i++) opt[i]=read();
for (int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if (opt[i]==2) a[i]=-a[i];
}a[0]=0;
for (int i=1;i<=n;i++) a[i]+=a[i-1];
Q=read();
for (int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+Q+1,cmp);
solve();
for (int i=1;i<=Q;i++) printf("%lld\n",ans[i]);
return 0;
}
版权声明：本文为ckr1225原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。