#include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define pll pair<ll, ll> #define vii vector<pii> #define vb vector<bool> #define vvb vector<vb> #define vl vector<ll> #define endl '\n' #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pb push_back #define ll long long #define f first #define s second using namespace std; int pot = 1; vi tree; void add(int x) { for(x+=pot; x; x/=2) tree[x]++; } int query(int k, int e = 1) { if(e*2 >= pot*2) return e-pot; if(tree[e*2] < k) return query(k-tree[e*2], e*2+1); return query(k, e*2); } int main() { turbo int n; cin >> n; while(pot < n) pot*=2; vi v(n); for(auto &it : v) cin >> it; int res = 0; for(int i = 0; i < n; i++) { tree = vi(pot*2, 0); for(int j = i; j < n; j++) { add(v[j]); int si = tree[1]; if(si&1) { if(query(si/2+1)*2 + si == n*2+1) res++; } else if(query(si/2) + query(si/2+1) + si == n*2+1) res++; } } cout << n*2+1 << ' ' << res << endl; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define pll pair<ll, ll> #define vii vector<pii> #define vb vector<bool> #define vvb vector<vb> #define vl vector<ll> #define endl '\n' #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pb push_back #define ll long long #define f first #define s second using namespace std; int pot = 1; vi tree; void add(int x) { for(x+=pot; x; x/=2) tree[x]++; } int query(int k, int e = 1) { if(e*2 >= pot*2) return e-pot; if(tree[e*2] < k) return query(k-tree[e*2], e*2+1); return query(k, e*2); } int main() { turbo int n; cin >> n; while(pot < n) pot*=2; vi v(n); for(auto &it : v) cin >> it; int res = 0; for(int i = 0; i < n; i++) { tree = vi(pot*2, 0); for(int j = i; j < n; j++) { add(v[j]); int si = tree[1]; if(si&1) { if(query(si/2+1)*2 + si == n*2+1) res++; } else if(query(si/2) + query(si/2+1) + si == n*2+1) res++; } } cout << n*2+1 << ' ' << res << endl; } |