一道题12

$n leq 100000$的$a$序列和$m leq n$的$b$序列，问$a$有多少子串和$b$能匹配。匹配：俩串长度相同，且俩串的数存在一种一一对应的关系使得每一对的和都$>=h$。

把$b$排个序，这样一个$a_i$就能配$b$的一个后缀。设$a_i$能配上后缀$p_i$。一个$b_j$能配上，必须有$>=j$个$p_i$会$<=j$，不然前缀$j$就配不满了。这个用线段树搞搞。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 //#include<math.h>
 5 //#include<queue>
 6 #include<algorithm>
 7 //#include<iostream>
 8 //#include<assert.h>
 9 using namespace std;
10 
11 int n,m,h;
12 #define maxn 300011
13 int a[maxn],b[maxn],p[maxn];
14 
15 struct SMT
16 {
17     struct Node
18     {
19         int ls,rs;
20         int Max; int add;
21     }a[maxn<<1];
22     int size,n;
23     void clear(int m) {size=0; n=m; a[0].Max=-1e9;}
24     void up(int x) {a[x].Max=max(a[a[x].ls].Max,a[a[x].rs].Max);}
25     void addsingle(int x,int v) {a[x].Max+=v; a[x].add+=v;}
26     void down(int x) {if (a[x].add) {addsingle(a[x].ls,a[x].add); addsingle(a[x].rs,a[x].add); a[x].add=0;}}
27     
28     void build(int &x,int L,int R)
29     {
30         x=++size;
31         if (L==R) {a[x].ls=a[x].rs=0; a[x].Max=L; return;}
32         int mid=(L+R)>>1;
33         build(a[x].ls,L,mid); build(a[x].rs,mid+1,R); up(x);
34     }
35     void build() {int x; build(x,1,n);}
36     int ql,qr,v;
37     void Add(int x,int L,int R)
38     {
39         if (ql<=L && R<=qr) {addsingle(x,v); return;}
40         down(x);
41         int mid=(L+R)>>1;
42         if (ql<=mid) Add(a[x].ls,L,mid);
43         if (qr>mid) Add(a[x].rs,mid+1,R);
44         up(x);
45     }
46     void add(int x,int y,int v) {if (x>y) return; ql=x; qr=y; this->v=v; Add(1,1,n);}
47     int Query(int x,int L,int R)
48     {
49         if (ql<=L && R<=qr) return a[x].Max;
50         down(x);
51         int mid=(L+R)>>1,ans=-1e9;
52         if (ql<=mid) ans=Query(a[x].ls,L,mid);
53         if (qr>mid) ans=max(ans,Query(a[x].rs,mid+1,R));
54         return ans;
55     }
56     int query(int x,int y) {ql=x; qr=y; return Query(1,1,n);}
57 }t;
58 
59 int main()
60 {
61     scanf("%d%d%d",&n,&m,&h);
62     for (int i=1;i<=m;i++) scanf("%d",&b[i]);
63     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
64     sort(b+1,b+1+m);
65     
66     t.clear(m); t.build();
67     int ans=0;
68     for (int i=1;i<=n;i++)
69     {
70         p[i]=lower_bound(b+1,b+1+m,h-a[i])-b;
71         t.add(p[i],m,-1);
72         if (i>m) t.add(p[i-m],m,1);
73         if (t.a[1].Max<=0) ans++;
74     }
75     printf("%d
",ans);
76     return 0;
77 }

View Code