给定排列
首先为了方便我们令
于是到此问题可转化为,求区间最大值最小值,然后再求区间等于
然后考虑如何维护区间等于 basic_string < pair < int, int > >
,存储对应值有多少个,合并的时候直接把两个加起来即可,然后去个重。同时此时查询的时候可以不用枚举
1341
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template< typename T = int >
25inline T read(void);
26
27int N, K;
28int val[MAXN];
29
30struct MyPair{
31 int first, second;
32 friend const bool operator < (const MyPair &a, const MyPair &b){
33 return a.first == b.first ? a.second < b.second : a.first < b.first;
34 }
35};
36
37struct Node{
38 basic_string < MyPair/*val, cnt*/ > vals;
39 int lz;
40 Node operator = (const Node &b){
41 this->vals = b.vals;
42 this->lz = b.lz;
43 return *this;
44 }
45 friend const Node operator + (const Node &a, const Node &b){
46 Node ret{a.vals + b.vals, 0};
47 sort(ret.vals.begin(), ret.vals.end());
48 for(auto it = ret.vals.begin(); next(it) != ret.vals.end();)
49 if(it->first == next(it)->first)next(it)->second += it->second, it = ret.vals.erase(it);
50 else advance(it, 1);
51 return ret;
52 }
53 friend Node operator += (Node &a, const int &val){
54 for(auto &nod : a.vals)nod.first += val;
55 a.lz += val;
56 return a;
57 }
58};
59class SegTree{
60private:
61 Node tr[MAXN << 2];
62
63
64
65public:
66 void Pushup(int p){tr[p] = tr[LS] + tr[RS];}
67 void Pushdown(int p){
68 if(!tr[p].lz)return;
69 tr[LS].lz = tr[RS].lz = tr[p].lz;
70 tr[LS] += tr[p].lz, tr[RS] += tr[p].lz;
71 tr[p].lz = 0;
72 }
73 void Build(int p = 1, int gl = 1, int gr = N){
74 if(gl == gr)return tr[p].vals += {gl = gr, 1}, void();
75 Build(LS, gl, MID), Build(RS, MID + 1, gr);
76 Pushup(p);
77 }
78 void Modify(int l, int r, int val, int p = 1, int gl = 1, int gr = N){
79 if(l <= gl && gr <= r)return tr[p] += val, void();
80 Pushdown(p);
81 if(l <= MID)Modify(l, r, val, LS, gl, MID);
82 if(r >= MID + 1)Modify(l, r, val, RS, MID + 1, gr);
83 Pushup(p);
84 }
85 Node Query(int l, int r, int p = 1, int gl = 1, int gr = N){
86 if(l <= gl && gr <= r)return tr[p];
87 Pushdown(p);
88 if(l > MID)return Query(l, r, RS, MID + 1, gr);
89 if(r < MID + 1)return Query(l, r, LS, gl, MID);
90 return Query(l, r, LS, gl, MID) + Query(l, r, RS, MID + 1, gr);
91 }
92}st;
93ll Cal(int R){
94 ll ret(0);
95 auto vals = st.Query(1, R).vals;
96 //r + k >= l + max - min
97 for(auto nod : vals)if(R + K >= nod.first)ret += nod.second;
98 return ret;
99}
100
101int mx[MAXN]/*Query Min*/, mn[MAXN]/*Query Max*/;
102int mxp(0), mnp(0);
103
104int main(){
105 N = read(), K = read();
106 for(int i = 1; i <= N; ++i)val[i] = read();
107 st.Build();
108 ll ans(0);
109 for(int R = 1; R <= N; ++R){
110 while(mxp && val[R] > val[mx[mxp]])st.Modify(mx[mxp - 1] + 1, mx[mxp], val[R] - val[mx[mxp]]), --mxp;
111 while(mnp && val[R] < val[mn[mnp]])st.Modify(mn[mnp - 1] + 1, mn[mnp], val[mn[mnp]] - val[R]), --mnp;
112 mx[++mxp] = mn[++mnp] = R;
113 ans += Cal(R);
114 // printf("R = %d, Cal = %lld\n", R, Cal(R));
115 }printf("%lld\n", ans);
116 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
117 return 0;
118}
119
120template < typename T >
121inline T read(void){
122 T ret(0);
123 int flag(1);
124 char c = getchar();
125 while(c != '-' && !isdigit(c))c = getchar();
126 if(c == '-')flag = -1, c = getchar();
127 while(isdigit(c)){
128 ret *= 10;
129 ret += int(c - '0');
130 c = getchar();
131 }
132 ret *= flag;
133 return ret;
134}
不过这个东西我们简单分析以下复杂度就会发现,每次合并和修改之后的 Pushup
都会使其重构然后耗费大量时间,所以最后复杂度是
然后对于 basic_string < pair < int, int > >
还有个很严重的问题,对于一般的 C++14 及以下都不会有任何问题,但是在 C++17 之后,因为 basic_string.h
中有如下语段:
31
2
3
然而引入的这个头文件中还存在如下语句:
11static_assert(is_trivial_v<_CharT> && is_standard_layout_v<_CharT>);
此时我们发现,这东西会 CE!测试后发现如下语段会输出
11cout << is_trivial < pair< int, int > >::value << endl;
众所周知 is_trivial
一般就是用于判断类型的构造函数是否为默认构造函数,而 pair
的构造函数似乎是用初始化列表写的,可能是因为这个原因,就会导致其无法通过这个 assert
,于是就寄了。然而 AT 上默认的不知道是 C++17 还是 20 或者更高,所以无法过编。这个或许可以通过一些高妙的方式解决,但是我不会,于是考虑自定义一个结构体实现跟 pair
一样但是使用默认构造函数即可。
所以话说回来,这个做法本身就是错误的,于是现在我们考虑正解:
思考什么东西比较好维护区间最值和区间等于 我不太喜欢分块这个复杂度不够优秀,所以这里就不给代码实现了,我们考虑一些更优秀的做法。
考虑分治,思路来自机房大佬 @sssmzy,发现对于每一个区间,如果我们令
具体地,对于维护答案的过程,我们发现最大值和最小值的位置无法确定,所以考虑枚举最大值在左侧或右侧,以左侧为例子,我们按照类似猫树的思想,从
当前区间算完之后二分下去分别求解即可,这样最终复杂度
871
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27int N, K;
28int a[MAXN];
29ll ans(0);
30int mx[MAXN], mn[MAXN];
31int buc[MAXN << 1];
32
33void Divide(int gl = 1, int gr = N){
34 if(gl == gr)return ++ans, void();
35 int MID = (gl + gr) >> 1;
36 mx[MID] = mn[MID] = a[MID], mx[MID + 1] = mn[MID + 1] = a[MID + 1];
37 for(int i = MID - 1; i >= gl; --i)mx[i] = max(mx[i + 1], a[i]), mn[i] = min(mn[i + 1], a[i]);
38 for(int i = MID + 2; i <= gr; ++i)mx[i] = max(mx[i - 1], a[i]), mn[i] = min(mn[i - 1], a[i]);
39 int sp1(MID), sp2(MID);
40 for(int l = MID; l >= gl; --l){
41 while(sp1 + 1 <= gr && mx[sp1 + 1] <= mx[l])++sp1, buc[sp1 + mn[sp1]]++;
42 while(sp2 + 1 <= gr && mn[sp2 + 1] >= mn[l])++sp2, buc[sp2 + mn[sp2]]--;
43 for(int k = 0; k <= K; ++k){
44 int r = l + mx[l] - mn[l] - k;
45 int idx = l + mx[l] - k;
46 if(MID + 1 <= r && r <= min(sp1, sp2))++ans;
47 if(sp2 < sp1 && idx > 0)ans += buc[idx];
48 }
49 }for(int i = MID + 1; i <= gr; ++i)buc[i + mn[i]] = 0;
50 sp1 = MID + 1, sp2 = MID + 1;
51 for(int r = MID + 1; r <= gr; ++r){
52 while(sp1 - 1 >= gl && mx[sp1 - 1] <= mx[r])--sp1, buc[sp1 - mn[sp1] + N]++;
53 while(sp2 - 1 >= gl && mn[sp2 - 1] >= mn[r])--sp2, buc[sp2 - mn[sp2] + N]--;
54 for(int k = 0; k <= K; ++k){
55 int l = r - mx[r] + mn[r] + k;
56 int idx = r - mx[r] + k + N;
57 if(max(sp1, sp2) <= l && l <= MID)++ans;
58 if(sp1 < sp2 && idx > 0)ans += buc[idx];
59 }
60 }for(int i = gl; i <= MID; ++i)buc[i - mn[i] + N] = 0;
61 Divide(gl, MID), Divide(MID + 1, gr);
62}
63
64int main(){
65 N = read(), K = read();
66 for(int i = 1; i <= N; ++i)a[i] = read();
67 Divide();
68 printf("%lld\n", ans);
69 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70 return 0;
71}
72
73template < typename T >
74inline T read(void){
75 T ret(0);
76 int flag(1);
77 char c = getchar();
78 while(c != '-' && !isdigit(c))c = getchar();
79 if(c == '-')flag = -1, c = getchar();
80 while(isdigit(c)){
81 ret *= 10;
82 ret += int(c - '0');
83 c = getchar();
84 }
85 ret *= flag;
86 return ret;
87}
update-2022_11_22 初稿