CF877F 题解
提供一个扫描线 + 根号分治做法。
首先，可以把题目的条件转化成求 $sum_r-sum_{l-1}=k$ 的区间数。
考虑扫描线，当区间的右端点从 $r-1$ 移动到 $r$ 时，新增的区间的左端点就是所有满足 $sum_{l-1}=sum_r-k,l\le r$ 的 $l$。这时我们对 $sum_{l-1}$ 的出现次数按 $B$ 进行分治。
具体的，如果出现次数 $\le B$ ，那么我们这一次至多会修改 $B$ 个位置，而查询只有一次，于是可以采用 $O(1)-O(\sqrt{n})$ 的分块来维护；如果出现次数 $>B$，这样的数至多有 $\dfrac{n}{B}$ 个，我们可以对每个数都维护一个数据结构，要求支持区间加以及区间和，而每次加的操作只有 $O(1)$ 次，但是每个询问都要对每个数进行查询，共 $\dfrac{n}{B}$ 次，于是可以采用 $O(\sqrt{n})-O(1)$ 的分块（具体可见
总复杂度 $O(n\sqrt{n}+q\sqrt{n}+nB+q\dfrac{n}{B})$，$B$ 取 $\sqrt{n}$ 时就可以在 $O(n\sqrt{n}+q\sqrt{n})$ 的复杂度内解决这道题。
1 const int N=100501,B=1000; 2 int n,k,Q; 3 int t[N],a[N],tot,bl[N],L[N],R[N]; 4 ll pre[N],ans[N],st[N]; 5 vector<pair<int,int> >qu[N]; 6 map<ll,int>mp; 7 struct Brick{ 8 ll sum[N],sumb[N]; 9 inline void modify(int x){sum[x]++,sumb[bl[x]]++;} 10 inline ll query(int l,int r){ 11 if(bl[l]==bl[r]){ 12 ll ans=0; 13 for(int i=l;i<=r;i++)ans+=sum[i]; 14 return ans; 15 } 16 ll ans=0; 17 for(int i=l;i<=R[bl[l]];i++)ans+=sum[i]; 18 for(int i=bl[l]+1;i<bl[r];i++)ans+=sumb[i]; 19 for(int i=L[bl[r]];i<=r;i++)ans+=sum[i]; 20 return ans; 21 } 22 }T; 23 vector<int>hav[N],big; 24 int id[N],cnt; 25 struct Bri{ 26 vector<ll>pre,sum,tag; 27 int n; 28 inline void init(int m){n=m;pre.resize(n+1),sum.resize(n+1),tag.resize(n+1);} 29 inline void add(int x,int k){ 30 for(int i=x;i<=R[bl[x]];i++)pre[i]+=1ll*k*(i-x+1); 31 for(int i=bl[x]+1;i<=bl[n];i++)sum[i]+=1ll*k*(1-x),tag[i]+=k; 32 } 33 inline void add(int l,int r,int k){add(l,k);if(r<n)add(r+1,-k);} 34 inline ll query(int x){return pre[x]+sum[bl[x]]+1ll*tag[bl[x]]*x;} 35 inline ll query(int l,int r){return query(r)-query(l-1);} 36 }b[N/B+50]; 37 int low[N/B+50][N],upp[N/B+50][N]; 38 int main(){ 39 n=read(),k=read(); 40 for(int i=1;i<=n;i++)t[i]=read(); 41 for(int i=1;i<=n;i++)a[i]=read(),pre[i]=pre[i-1]+(t[i]==1?a[i]:-a[i]); 42 for(int i=0;i<n;i++)st[++tot]=pre[i]; 43 sort(st+1,st+tot+1); 44 tot=unique(st+1,st+tot+1)-st-1; 45 for(int i=1;i<=tot;i++)mp[st[i]]=i; 46 for(int i=0;i<n;i++)hav[mp[pre[i]]].push_back(i); 47 for(int i=1;i<=n;i++){ 48 bl[i]=(i-1)/B+1; 49 if(bl[i]^bl[i-1])L[bl[i]]=i; 50 R[bl[i]]=i; 51 } 52 for(int i=1;i<=tot;i++)if((int)hav[i].size()>B)big.push_back(i),id[i]=++cnt; 53 for(int i=0;i<n;i++)if(id[mp[pre[i]]]){ 54 int x=id[mp[pre[i]]]; 55 low[x][i+1]++; 56 upp[x][i+2]++; 57 } 58 for(int i=1;i<=cnt;i++){ 59 upp[i][0]=1; 60 for(int j=1;j<=n;j++)low[i][j]+=low[i][j-1],upp[i][j]+=upp[i][j-1]; 61 b[i].init(low[i][n]); 62 } 63 Q=read(); 64 for(int t=1;t<=Q;t++){ 65 int l=read(),r=read(); 66 qu[r].push_back({l,t}); 67 } 68 for(int i=1;i<=n;i++){ 69 ll cur=pre[i]-k; 70 if(mp[cur]){ 71 int x=mp[cur]; 72 int len=hav[x].size(); 73 if(len<=B){ 74 for(auto j:hav[x]){ 75 if(j>=i)break; 76 T.modify(j+1); 77 } 78 } 79 else{ 80 int y=id[x]; 81 b[y].add(1,low[y][i],1); 82 } 83 } 84 for(auto j:qu[i]){ 85 int l=j.first,id=j.second; 86 ans[id]+=T.query(l,i); 87 for(int k=1;k<=cnt;k++)ans[id]+=b[k].query(upp[k][l],low[k][i]); 88 } 89 } 90 for(int i=1;i<=Q;i++)write(ans[i]),putchar('\n'); 91 return 0; 92 }