题意：给2个数字序列 a 和 b ，问按从小到达排序后，a中的哪些子串与b的名次匹配。 a 的长度 N≤100,000，b的长度 M≤25,000，数字的大小 K≤25。
解法：【思考】1.X 暴力。枚举 a 中的子串，选出来排序后比对名次。O(n* m log m *m)=O(n*m^2*log m)。
2.X 暴力+树状数组优化。枚举 a 中的子串，选出来后比较前缀名次（P.S.这种转化常出现，比如：【洛谷 p3368】模板-树状数组 2（数据结构） 就是将个体转化为前缀。），看加上自己的之前小于等于和等于该数的个数是否相等。O(n*m log m)。
3.√ kmp+树状数组优化。直接kmp匹配 a串和 b串，next[ ]预处理 b串，再在kmp时看前缀名次来比较。（这个要kmp理解得很好才能在处理树状数组时处理得很好，我现在思绪混乱啊......代码就算了......qwq）
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 const int N=100010,M=25010,K=30;
8 struct node{int x,y,d;}b[M],a[N];
9 int a[N],b[M],next[M];
10 int cnt=0,s[N];
11 int ca[K],cb[K];
12
13 int lowbit(int x) {return x&-x;}
14 int change(int x,int d)
15 {
16 for (int i=x;i<=n;i+=lowbit(i))
17 ca[i]+=d;
18 }
19 int getcount(int x)
20 {
21 int sum=0;
22 for (int i=x;i>=1;i-=lowbit(i))
23 sum+=ca[i];
24 return sum;
25 }
26 int change_2(int x,int d)
27 {
28 for (int i=x;i<=m;i+=lowbit(i))
29 cb[i]+=d;
30 }
31 int getcount_2(int x)
32 {
33 int sum=0;
34 for (int i=x;i>=1;i-=lowbit(i))
35 sum+=cb[i];
36 return sum;
37 }
38 void init_kmp()
39 {
40 memset(cb,0,sizeof(cb));
41 memset(next,0,sizeof(next));
42 int p=0,x=0,y=0;
43 next[1]=0;
44 for (int i=2;i<=m;i++)
45 {
46 while ((b[i].x!=b[p+1].x||b[i].y!=b[p+1].y) && p)
47 {
48 p=next[p];
49 }
50 if (b[i].x==b[p+1].x&&b[i].y==b[p+1].y)
51 {
52 p++;
53 add_2(b[i].d,1);
54 }
55 next[i]=p;
56 }
57 }
58 void kmp()
59 {
60 int p=0;
61 for (int i=1;i<=n;i++)
62 {
63 int x=getcount_2(a[i].d-1);
64 while ((a[i].x-(a[i-p].x+a[i-p].y)!=b[p+1].x||a[i].y!=b[p+1].y) && p) p=next[p];
65 if (a[i].x==b[p+1].x&&a[i].y==b[p+1].y) p++;
66 if (p==m) s[++cnt]=i;
67 }
68 }
69 int main()
70 {
71 freopen("a.in","r",stdin);
72 int n,m,k;
73 scanf("%d%d%d",&n,&m,&k);
74 //memset(ca,0,sizeof(ca));
75 for (int i=1;i<=n;i++)
76 {
77 scanf("%d",&a[i].d);
78 /*change(a[i].d,1);
79 a[i].x=getcount(a[i].d);
80 a[i].y=a[i].x-getcount(a[i].d-1);*/
81 }
82 //memset(cb,0,sizeof(cb));
83 for (int i=1;i<=m;i++)
84 {
85 scanf("%d",&b[i].d);
86 /*change_2(b[i].d,1);
87 b[i].x=getcount_2(b[i].d);
88 b[i].y=b[i].x-getcount_2(b[i].d-1);*/
89 }
90 init_kmp();
91 kmp();
92 printf("%d\n",cnt);
93 for (int i=1;i<=cnt;i++)
94 printf("%d ",s[i]);
95 return 0;
96 }