1.7万

Heyya
imtx

Chessma
oyrzk

123121s

Char

LN

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 200010;
int c2[N],c5[N],s2[N],s5[N];
int n, k;

int main ()
{
int T;
cin >> T;
while(T --){
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
c2[i] = c5[i] = 0;
int x;
cin >> x;
while(x % 2 == 0) c2[i] ++, x /= 2;
while(x % 5 == 0) c5[i] ++, x /= 5;
s2[i] = s2[i - 1] + c2[i];
s5[i] = s5[i - 1] + c5[i];
}
LL res = 0;
for(int i = 1; i <= n; i ++){
int l1 = lower_bound(s2 + i, s2 + 1 + n, s2[i - 1] + k) - s2;
int r1 = upper_bound(s2 + i, s2 + 1 + n, s2[i - 1] + k) - s2;
int l2 = lower_bound(s5 + i, s5 + 1 + n, s5[i - 1] + k) - s5;
int r2 = upper_bound(s5 + i, s5 + 1 + n, s5[i - 1] + k) - s5;
int L = max(l1, l2), R = max(r1, r2);
res += max(0, R - L);
}
cout << res << endl;
}
return 0;
}


https://codeforces.com/contest/229/problem/B

4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0

3 1
1 2 3
0
1 3
0

### v存储所有连续的区间

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 100010, M = 2 * N;
const long long INF = 1e18;

int n, m;
int e[M], w[M], ne[M], h[N], idx;
vector<pair<int,int>> v[N];
LL dis[N];
bool st[N];

void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void D()
{
for(int i = 1; i <= n; i ++) dis[i] = 1e18;

if(v[1].size() > 0){
if(v[1][0].first == 0) dis[1] = v[1][0].second + 1;
else dis[1] = 0;
}
else dis[1] = 0;

priority_queue<PLI, vector<PLI>, greater<PLI>> heap;
heap.push({dis[1], 1});
while(heap.size()){
auto t = heap.top();
heap.pop();
int u = t.second;
if(st[u]) continue;
st[u] = true;

for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];

if(dis[j] > dis[u] + w[i]){
dis[j] = dis[u] + w[i];
if(v[j].size() > 0 && j != n)
{
int l = 0, r = v[j].size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(v[j][mid].first <= dis[j]) l = mid;
else r = mid - 1;
}
if(v[j][r].first <= dis[j] && v[j][r].second >= dis[j]) dis[j] = v[j][r].second + 1;
}

heap.push({dis[j], j});
}
}
}
}
int main ()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --){
int a, b, c;
cin >> a >> b >> c;
}
for(int i = 1; i <= n; i ++){
int k;
cin >> k;
vector<int> w;
if(k > 0)
{
for(int j = 0; j < k; j ++)
{
int x;
cin >> x;
w.push_back(x);
}
for(int a = 0; a < k; a ++)
{
int b = a;
while(b + 1 < k && w[b + 1] == w[b] + 1) b ++;

v[i].push_back({w[a], w[b]});
a = b;
}
}
}

D();
if(dis[n] > INF / 2) puts("-1");
else cout << dis[n] << endl;
return 0;
}



https://codeforces.com/problemset/problem/1759/G

6
6
4 3 6
4
2 4
8
8 7 2 3
6
6 4 2
4
4 4
8
8 7 4 5

1 4 2 3 5 6
1 2 3 4
-1
5 6 3 4 1 2
-1
1 8 6 7 2 4 3 5

### 并查集能快速判断 如果一个数s被使用了，那么它的祖先指向s - 1的祖先

#include <bits/stdc++.h>

using namespace std;

vector<int> p;

int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void solve()
{
int n;
cin >> n;
vector<int> ans(2 * n + 1), b(n + 1);
p.resize(n + 1);
vector<bool> st(n + 1, false);
for(int i = 0; i <= n; i ++) p[i] = i;

for(int i = 1; i <= n / 2; i ++){
cin >> b[i];
int pb = find(b[i]), pa = find(b[i] - 1);
p[pb] = pa;
}
bool ok = true;
for(int i = n / 2; i >= 1; i --){
if(st[b[i]]){
ok = false;
break;
}
ans[i * 2] = b[i];
st[b[i]] = true;
int t = find(b[i] - 1);
if(t == 0)
{
ok = false;
break;
}
else{
ans[i * 2 - 1] = t;
st[t] = true;
p[t] = find(t - 1);
}
}
if(ok){
for(int i = 1; i <= n; i ++){
cout << ans[i] << ' ';
}
cout << endl;
}
else puts("-1");
}
int main ()
{
int T;
cin >> T;
while(T --){
solve();
}
return 0;
}


#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;
int n;
int a[N];

struct node{
int l, r;
LL s;
}tr[N << 2];

void build(int u, int l, int r)
{
if(l == r){
tr[u] = {r, r, 0};
return;
}
tr[u] = {l, r, 0};
int mid = (l + r) / 2;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void pushup(int u){
tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
}
void update(int u, int x, int c){
if(tr[u].l == tr[u].r){
tr[u].s = c;
return;
}
int mid = (tr[u].l + tr[u].r) / 2;
if(x <= mid) update(u << 1, x, c);
else update(u << 1 | 1, x, c);
pushup(u);
}
int query(int u, LL mid, int fg){
if(tr[u].s < mid) return fg == 0? 1e9: -1e9;
if(tr[u].l == tr[u].r){
if(fg == 0){
if(tr[u].s == mid) return tr[u].r + 1;
else return tr[u].r;
}
else{
if(tr[u].s ==mid) return tr[u].r - 1;
else return tr[u].r;
}
}
if(fg == 0){
if(mid <= tr[u << 1].s){
return query(u << 1, mid, fg);
}
else{
return query(u << 1 | 1, mid - tr[u << 1].s, fg);
}
}
else{
if(tr[u << 1 | 1].s >= mid){
return query(u << 1 | 1, mid, fg);
}
else{
return query(u << 1, mid - tr[u << 1 | 1].s, fg);
}
}
}
int main(){
cin >> n;
build(1, 1, n);
for(int i = 1; i <= n; i ++){
cin >> a[i];
update(1, i, a[i]);
}
int q;
cin >> q;
while(q --){
int k, x, y;
cin >> k >> x;
if(k == 1){
cin >> y;
update(1, x, y);
}
else{
LL l = 0, r = 1e14;
while(l < r){
LL mid =(l + r) / 2;
if(query(1, mid, 1) - query(1, mid, 0) + 1 <= x) r = mid;
else l = mid + 1;
}
cout << r << endl;
}
}
return 0;
}


https://codeforces.com/problemset/problem/1693/B

4
2
1
1 5
2 9
3
1 1
4 5
2 4
6 10
4
1 2 1
6 9
5 6
4 5
2 4
5
1 2 3 4
5 5
4 4
3 3
2 2
1 1

1
2
2
5

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 200010;
int e[N], ne[N], h[N], idx;
LL s[N];
int dp[N];
int n;
PII v[N];

e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u){
if(h[u] == -1){
s[u] = v[u].second;
dp[u] = 1;
return dp[u];
}
LL s1 = 0;
int s2 = 0;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
dfs(j);
s1 += s[j];
s2 += dp[j];
}
if(s1 > v[u].second){
s[u] = v[u].second;
dp[u] = s2;
}
else if(s1 >= v[u].first && s1 <= v[u].second){
s[u] = s1;
dp[u] = s2;
}
else{
s[u] = v[u].second;
dp[u] = s2 + 1;
}
return dp[u];
}
void solve(){
cin >> n;
memset(h, -1, sizeof h);
memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; i ++) s[i] = 0;

idx = 0;
for(int i = 2; i <= n; i ++){
int x;
cin >> x;
}
for(int i = 1; i <= n; i ++) cin >> v[i].first >> v[i].second;

cout << dfs(1) << endl;
}
int main ()
{
int T;
cin >> T;
while(T --){
solve();
}
return 0;
}


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>

using namespace std;

const int N = 30010, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N], q[N];
bitset<N> f[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;

while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if ( -- d[j] == 0)
q[ ++ tt] = j;
}
}
}

int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
d[b] ++ ;
}

topsort();

for (int i = n - 1; i >= 0; i -- )
{
int j = q[i];
f[j][j] = 1;
for (int k = h[j]; ~k; k = ne[k])
f[j] |= f[e[k]];
}

for (int i = 1; i <= n; i ++ ) printf("%d\n", f[i].count());

return 0;
}


#include <bits/stdc++.h>

using namespace std;

int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> d(n + 1, 0);
for(int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
d[a] ++;
g[b].push_back(a);
}
queue<int> q;
vector<int> ans(n + 1, 0);
for(int i = 1; i <= n; i ++)
{
if(d[i] == 0){
q.push(i);
ans[i] = 100;
}
}
while(q.size())
{
auto t = q.front();
q.pop();
for(int j : g[t]){
if(-- d[j] == 0){
ans[j] = ans[t] + 1;
q.push(j);
}
}
}
int res = 0;
bool ok = true;
for(int i = 1; i <= n; i ++){
res += ans[i];
if(!ans[i]) ok = false;
}
if(ok)
cout << res;
else puts("Poor Xed");
return 0;
}


#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n;
int d[N];

int main()
{
cin >> n;
vector<vector<int>> g(n + 1);

for(int i = 1; i <= n; i ++)
{
int x;
while(cin >> x, x != 0){
d[x] ++;
g[i].push_back(x);
}
}
queue<int> q;
for(int i = 1; i <= n; i ++) if(d[i] == 0) q.push(i);

vector<int> ans;
while(q.size())
{
int t = q.front();
ans.push_back(t);
q.pop();
for(int y : g[t]){
if(-- d[y] == 0){
q.push(y);
}
}
}
for(auto &x : ans) cout << x << ' ';
return 0;
}


https://codeforces.com/problemset/problem/883/I

5 2
50 110 130 40 120

4 1
2 3 4 1

#include <bits/stdc++.h>

using namespace std;

const int N = 300010;
int a[N];
int n, k;

bool check(int mid)
{
vector<bool> dp(n + 1, false);
dp[0] = true;
for(int i = 1, j = 1; i <= n; i ++){
while(j <= i && a[i] - a[j] > mid || dp[j - 1] == false) j ++;

if(i - j + 1 >= k) dp[i] = true;
}
return dp[n] == true;
}
int main ()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];

sort(a + 1, a + 1 + n);
int l = 0, r = 1e9;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}


https://codeforces.com/problemset/problem/1118/D2

5 8
2 3 1 1 2

4

7 10
1 3 4 2 1 4 2

2

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 200010;
int n, m;
int a[N];
LL s[N];

bool check(int mid){
int c = 0;
int i, j;
for(i = 1, j = 1; i <= n; i ++){
if(i - j + 1 > mid){
j = i;
c ++;
}
if(a[i] - c <= 0) break;
}

LL sum = s[i - 1] - 1ll * (c - 1) * c / 2 * mid - 1ll * c * (i - j);

return sum >= m;
}
int main ()
{
cin >> n >> m;
LL res = 0;
for(int i = 1; i <= n; i ++){
cin >> a[i];
if(a[i] >= 0)
res += a[i];
}
if(res < m){
puts("-1");
}
else{
sort(a + 1, a + 1 + n, greater<>());
for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];

int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
}
return 0;
}