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 }
标签：ll,int,题解,sum,CF877F,sqrt,bl,id From： https://www.cnblogs.com/Xttttr/p/17725161.html