前言(feihua):
这个题目折磨了我大概两个小时，我是在图论的题单里面看到这道题目的。一开始看着，感觉有点像数据结构，但是既然是放在图论里面，怎么可能是单纯的数据结构题！（啪啪打脸，还真的可以纯数据结构）
想出来了一个合理的图论掺杂数据结构的算法，但是我太菜了，找ZCW神仙问了3次才最终写出代码...
思路:
首先这种类型的题目的思路，首先将a数组中的元素a[i]转化为h-a[i].
然后建图，连接所有b[j]使得b[j] >= h-a[i],表示b[j]是可以和a[i]匹配的，但是有个问题，那就是n和m大到了1.5 * 10^5,边数可能卡到特别多，然后就炸了.......
但是不慌，我接着想到了，把a(转化成h-a[i]后的数组),b数组排序.
排序后:
假如b[j-1]可以连到a[i]( 也就是b[j-1] >=a[i]),毫无疑问b[j]也可以连到a[i],(b[j] >= b[j-1] >= a[i])，这时候b[j]就直接连到b[j-1],然后再看有哪些是b[j]能连而 b[j-1]不能连的。
这样存的边数大概是 n + m 条
此时我们发现这样的图构成了一棵树，而且对于a中的元素必定是叶子节点.
以样例为例:
input:
5 2 10
5 3
1 8 5 5 7
output: 2
不难发现能够成功匹配的是[2,3]以及[4,5] 按照我的处理方式来做，首先将a数组转化为:
92 5 5 3
然后将a数组从小到大排序:
2 3 5 5 9
同时将b数组从小到大排序:
35
接着进行连边:
b[1] ---> a[1] (b[1] >= a[1])b[1] ---> a[2] (b[1] >= a[2])
b[2] ---> b[1] (b[2] >= b[1](此刻发现b[1]已经无法与a[3]匹配了)b[2] ---> a[3] (b[2] >= a[3])
b[2] ---> a[4] (b[2] >= a[4])
b[2] ---> a[5] (b[2] >= a[5])然后就形成了一棵树,带括号的表示的是a数组中的元素编号:
2
/
/1(3)(4)(5)
/
(1) (2)
但是接下来要查询的是原来a中的编号，我们需要将排序后的a[i]在原来的未排序中数组a中对应的位置找出来：
例如现在a[1]对应的是原来没有排序的a[2]
现在的a[2] 对应原来的a[5]，我们在树上把编号还原
2
/
/1(3)(4)(1)
/
(2) (5)
接着进入了判断环节，类似于滑动窗口，我们观察到如果判断了当前连续子序列，那么下一个连续子序列就只要删除一个点并且加入一个点
所以我们需要在logn的时间内判断是否可行。
以样例判断 [3,4]为例，我们发现，假如一个非叶子节点它的深度小于 它相连的叶子节点数与它的所有祖先节点连接的叶子节点的和
（这里的相连指的是现在还在树上的，例如[3,4],现在只有3和4这两个a中元素节点在树上，这里点"2"就有2个直接相连的叶子节点，但是它的深度为1）就无解
相当于维护一个前缀和，维护到当前这个非叶子节点它的祖先与它一共有多少个叶子节点，同时减去这个非叶子节点的深度，如果整棵树上没有一个非叶子节点的对应的权值大于0，那么ans++。
所以我们可以借助线段树求解，每次判断连续子序列时只会有一个节点被从树上删去，也只有一个节点被增加，所以就相当于区间修改以及求最大值的线段树了!
CODE:
很丑，辣眼睛,不建议观看，按照思路来写就行！
#include <bits/stdc++.h> using namespace std; #define int long long int n,m,h; int b[500105],f[500150]; struct node{int data,num;}a[500150]; struct tree{int l,r,Max,data,laz;}T[500150]; inline int read(); void build_tree(int l,int r,int x); void pushdown(int x); void ad(int x,int k); void add(int l,int r ,int x,int k); int get(int l,int r,int x); int cmp(node A,node B){return A.data < B.data;} signed main(){ int res = 0; n = read () , m = read () , h = read(); for (int i = 1 ; i <= m ; i ++)b[i] = read(); for (int i = 1 ; i <= n ; i ++)a[i].data = read(),a[i].num = i; for (int i = 1 ; i <= n ; i ++)a[i].data = h - a[i].data; sort ( a + 1 , a + 1 + n , cmp );sort( b + 1 , b + 1 + m ); int head = m , flag = 0;; for (int i = 1 ; i <= n ; i ++){ while (b[m-head+1] < a[i].data)head--; if (head <= 0){head++;break;} f[a[i].num] = head; } build_tree(1,m,1); for (int i = 1 ; i <= m ; i ++) add(i,i,1,-i); for (int i = 1 ; i <= n - m +1 ; i ++){ int l = i , r = i + m - 1; if (l == 1){ for (int j = l ; j <= r ; j ++){ if(f[j] != 0) add(f[j],m,1,1); else flag = j ; } if(get(1,m,1) <= 0 && flag == 0)res += 1; } else { int X = f[l-1] , Y = f[r]; if( X == 0 || Y == 0){ if (X == 0)add(Y,m,1,1),flag = X; else add(X,m,1,-1),flag = Y; } else{ if(Y > X) add(X,Y-1,1,-1); if(X > Y) add(Y,X-1,1,1); } if(get(1,m,1) <= 0 && l > flag)res += 1; } } cout << res; return 0; } int get(int l,int r,int x){ int Max = -0x3f; if( T[x].l >= l && T[x].r <= r)return T[x].Max; pushdown(x); int mid = ( T[x].l + T[x].r ) >> 1; if( l <= mid)Max = max(get(l,r,x*2),Max); if( r > mid)Max = max(get(l,r,x*2+1),Max); return Max; } inline int read(){ int x = 0 , flag = 1; char ch = getchar(); for ( ; ch > '9' || ch < '0' ; ch = getchar())if(ch == '-')flag = -1; for ( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - 48 ; return x * flag; } void build_tree(int l,int r,int x){ T[x].l = l , T[x] . r = r; if (T[x].l == T[x].r){T[x].Max = 0;return ;} int mid = ( l + r ) >> 1; build_tree(l,mid,x*2);build_tree(mid+1,r,x*2+1); T[x].Max = max(T[x*2+1].Max , T[x*2].Max); } void ad(int x,int k){ T[x].Max += k; T[x].laz += k; } void pushdown(int x){ if(T[x].laz == 0)return ; ad(x*2,T[x].laz); ad(x*2+1,T[x].laz); T[x].laz = 0; } void add(int l ,int r ,int x, int k ){ if (T[x].l >= l && T[x].r <= r){ ad(x,k); return ; }pushdown(x); int mid = (T[x]. l + T[x] . r) >> 1; if (l <= mid)add(l,r,x*2,k); if (r > mid)add(l,r,x*2+1,k); T[x].Max = max(T[x*2].Max,T[x*2+1].Max); }