手机可以做网站,wordpress 自动别名,手机网站建站费用,包工头接活app哪个好https://www.luogu.com.cn/problem/CF1762F
分析性质#xff0c;就是我们选的数要么递增#xff0c;要么递减#xff08;非严格#xff09;然后很明细是ds套dp#xff0c; f i f_i fi 表示以 i i i 开头的答案然后考虑如何转移#xff08;ds套dp难点反而在转移而不是…https://www.luogu.com.cn/problem/CF1762F
分析性质就是我们选的数要么递增要么递减非严格然后很明细是ds套dp f i f_i fi 表示以 i i i 开头的答案然后考虑如何转移ds套dp难点反而在转移而不是状态因为要考虑如何和ds结合转移的话要么从位置考虑要么从值域考虑从值域考虑就从后面比它大且最小的转移似乎不知道怎么搞从位置考虑就是从第一个在 [ a i , a i k ] [a_i,a_ik] [ai,aik] 内的数转移。我们考虑会漏掉值域在 [ a i 1 , a j − 1 ] [a_i1,a_j-1] [ai1,aj−1] 的数但这可以直接套ds来做了。至于大于 a j a_j aj 的会在 f j f_j fj 里算
#includebits/stdc.h
using namespace std;
#define int long long
inline int read(){int x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 500010
//#define M
//#define mo
struct node {int x, id; bool operator (const node A) const {return id A.id; }
}b[N];
int n, m, i, j, k, T;
int ans, a[N], mp[N], nxt[N], f[N], l;
setnodes;
setnode::iterator it; struct Binary_tree {int cnt[N]; void add(int x, int y) {while(xN) cnt[x]y, xx-x; }int que(int x) {int ans 0; while(x) anscnt[x], x-x-x; return ans; }
}Bin;void calc() {for(i1; in; i) b[i].x a[i], b[i].id i; auto cmp [] (node x, node y) - bool {if(x.x y.x) return x.id y.id; return x.x y.x; }; sort(b1, bn1, cmp); s.clear(); for(il1; in; i) {while(b[l].xb[i].xk) s.erase(b[l]), l; it s.upper_bound({0, b[i].id}); if(it s.end()) nxt[b[i].id] 0; else nxt[b[i].id] (it - id); s.insert(b[i]); }
// for(i 1; i n; i) printf(%d , nxt[i]); printf(\n); for(in; i1; --i) {jnxt[i]; f[i]f[j]1; if(nxt[i]0) f[i]Bin.que(a[i]k)-Bin.que(a[i]-1); else f[i]Bin.que(a[nxt[i]]-1)-Bin.que(a[i]-1); ansf[i]; Bin.add(a[i], 1);
// printf(%lld (%lld %lld), f[i], f[j]); }
// printf(\n); for(i1; in; i) Bin.add(a[i], -1);
}signed main()
{
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);Tread();while(T--) {nread(); kread(); ans0; for(i1; in; i) {a[i]read(), mp[a[i]], ans-mp[a[i]]; }
// printf( %lld\n, ans); calc(); reverse(a1, an1); calc(); for(i1; in; i) mp[a[i]]0; printf(%lld\n, ans); }return 0;
}
