6222

h._
e.Gravity

kzyz

hliatmy
Acwing_ikun
_C_

..-
lorendw7
AᴄWing
yxc的小迷妹

17637048556

##### #847 div3
###### B:

void solved()
{
int n, m, s;
cin >> n >> m >> s;

int mxx  = m - s;

ans[1] = mxx;

s -= n - 1;

for(int i = 2; i <= n; i++) ans[i] = 1;

for(int i = 2; i <= n; i++)
{

if(s - (mxx - 1) >= 0)
{
s -= mxx - 1;
ans[i] += mxx - 1;
}else
{
ans[i] += s;
break;
}
}

for(int i = 1; i <= n; i++) cout << ans[i] << " ";
cout << endl;
}

###### C：

void solved()
{

memset(cnt, 0, sizeof cnt);
memset(w, 0, sizeof w);

cin >> n;

for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n - 1; j++)
{
int x;
cin >> x;
cnt[j][x]++;
if(!w[j][0]) w[j][0] = x;
else
{
if(x != w[j][0]) w[j][1] = x;
}
}
}

int last = 0;

for(int i = n - 1; i >= 1; i--)
{

if(i == n - 1)
{
if(cnt[i][w[i][0]] > cnt[i][w[i][1]]) ans[i + 1] = w[i][0], last = w[i][1];
else ans[i + 1] = w[i][1], last = w[i][0];
continue;
}

if(i == 1)
{
if(cnt[i][w[i][0]] > cnt[i][w[i][1]]) ans[i] = w[i][0], ans[i + 1] = w[i][1];
else ans[i] = w[i][1], ans[i + 1] = w[i][0];
continue;
}

if(w[i][0] == last)
{
ans[i + 1] = last;
last = w[i][1];
}else
{
ans[i + 1] = last;
last = w[i][0];
}

}

for(int i = 1; i <= n; i++) cout << ans[i] << " ";

cout << endl;

}

###### D：

void solved()
{
map<int, int> hs;
vector<int> a;

cin >> n;
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;

if(!hs[x])
{
a.push_back(x);
}
hs[x]++;
}

sort(a.begin(), a.end());

int mxx = hs[a[0]];
int ans = 0;
int len = a.size();

for(int i = 1; i < len; i++)
{
int x = a[i];

if(a[i] == a[i - 1] + 1)
{
if(hs[a[i - 1]] > hs[a[i]])
{
ans += (hs[a[i - 1]] - hs[a[i]]);
}
mxx = (hs[a[i]]);

}else
{
ans += mxx;
mxx = hs[a[i]];
}

mxx = max(mxx, hs[x]);
}

ans += mxx;

cout << ans << endl;

}

###### E：

void solved()
{
int x;
cin >> x;

int a = 0, b = 0;

if(x & 1)
{
cout << -1 << endl;
return;
}

for(int i = 1; i <= 30; i++)
{
if(x >> i & 1)
{
if(x >> (i - 1) & 1)
{
cout << -1 <<endl;
return;
}
}

if(x >> i & 1)
{
a += 1 << i;
a += 1 << (i - 1);
b += 1 << (i - 1);
}
}

cout << a << " " << b << endl;

}


##### 第三场：
###### B：

bool check(int mid)
{
int x = (n + 1) / 2;
if(mid + (mid + x - 1) / x * (mid - x) > n) return true;
else return false;

}

void solved()
{
cin >> n;

if(n == 1)
{
cout << 1 << endl;
return;
}
if(n == 2)
{
cout << -1 <<endl;
return;
}
int  l = 2, r = n;

while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid)) r = mid - 1;
else l = mid;
}

cout << l << endl;

}

###### C：

void solved()
{
cin >> n;

if(n <= 3 || (n == 7))
{
cout << -1 << endl;
return;
}

vector<int>ans(n + 10);
if(n % 4 == 0)
{
ans[1] = 3, ans[2] = 4, ans[3] = 1, ans[4] = 2;
int now = 4;

for(int i = 4; i <= n; i += 4)
{

now += 4;
ans[i + 1] = now - 1;
ans[i + 2] = now;
ans[i + 3] = now - 3;
ans[i + 4] = now - 2;
}
}else if(n % 4 == 1)
{
ans[1] = 4, ans[2] = 5, ans[3] = 1, ans[4] = 2, ans[5] = 3;

int now = 5;

for(int i = 5; i <= n; i += 4)
{

now += 4;
ans[i + 1] = now - 1;
ans[i + 2] = now;
ans[i + 3] = now - 3;
ans[i + 4] = now - 2;
}
}else if(n % 4 == 2)
{
int now = 6;
ans[1] = 3, ans[2] = 5, ans[3] = 6, ans[4] = 1, ans[5] = 2, ans[6] = 4;

for(int i = 6; i <= n; i += 4)
{

now += 4;
ans[i + 1] = now - 1;
ans[i + 2] = now;
ans[i + 3] = now - 3;
ans[i + 4] = now - 2;
}
}else if(n % 4 == 3)
{
ans[1] = 3, ans[2] = 4, ans[3] = 1, ans[4] = 6, ans[5] = 2, ans[6] = 8;
ans[7] = 5, ans[8] = 10, ans[9] = 11, ans[10] = 7, ans[11] = 9;
int now = 11;
for(int i = 11; i <= n; i += 4)
{

now += 4;
ans[i + 1] = now - 1;
ans[i + 2] = now;
ans[i + 3] = now - 3;
ans[i + 4] = now - 2;
}
}

for(int i = 1; i <= n; i++)
{
cout << ans[i] << " ";
}
}

###### G：

DFS 搜索即可，不过需要注意的是题目的数据很大，需要使用快速幂

long long qmi(long long a, long long b, int p)
{
long long res = 1;
while (b)
{

if (b & 1) res = (res % p) * (a % p) % p;

a = (a % p) * (a % p) % p;
b >>= 1;
}

return res;
}

void dfs(int u, int sum, int cnt)
{
if(zm[u] == '=' )
{
if(sum != ans) return;

int now = 0;
cout <<sz[0];
for(int i = 0; i < zm.size(); i++)
{
if(zm[i] != '?') cout << zm[i];
else cout << ss[now++];
cout <<sz[i + 1];

}
cout << endl;

exit(0);
}

ss[cnt] = '-';
dfs(u + 1, sum - sz[u + 1], cnt + 1);
ss[cnt] = '+';
dfs(u + 1, sum + sz[u + 1], cnt + 1);
ss[cnt] = '#';

if(sum > 0)
dfs(u + 1, qmi(sum, sum, sz[u + 1]), cnt + 1);
}
void solved()
{

cin >> s;

int num = 0;

for(int i = 0; i < s.size(); i++)
{

if(s[i] >= '0' && s[i] <= '9')
{
num += s[i] - '0';
num *= 10;

if(i == s.size() - 1)
{
sz.push_back(num / 10);
}

}else
{
sz.push_back(num / 10);
num = 0;
zm.push_back(s[i]);
}
}

ans = sz[sz.size() - 1];

dfs(0, sz[0], 0);
cout << -1;

}


##### 第二场：
###### C：

void push_up(int u)
{
tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
}

void push_down(int u)
{
Node &root = tr[u], &le = tr[u <<1], &ri = tr[u << 1 | 1];

if(root.lazy)
{
le.lazy += root.lazy;
ri.lazy += root.lazy;
le.cnt += (le.r - le.l + 1) * root.lazy;
ri.cnt += (ri.r - ri.l + 1) * root.lazy;

root.lazy = 0;
}
}

void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, 0};
return;
}

tr[u] = {l, r};

int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

push_up(u);
}

void modify(int u, int l, int r, int x)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].cnt += (tr[u].r - tr[u].l + 1) * x;
tr[u].lazy += x;
return;
}

push_down(u);

int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) modify(u << 1, l, r, x);
if(r > mid) modify(u << 1 | 1, l, r, x);

push_up(u);
}

LL query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].cnt;
}

push_down(u);
int mid = tr[u].l + tr[u].r >> 1;

LL ans = 0;

if(l <= mid) ans = (ans + query(u << 1, l, r)) % MOD;
if(r > mid) ans = (ans +query(u << 1 | 1, l, r)) % MOD;
return ans % MOD;

}

vector<PII> qj;

void solved()
{
cin >> n >> m;

int mxx = 0;

for(int i = 0; i < m; i++)
{
PII x;
cin >> x.first >> x.second;
qj.push_back(x);
mxx = max(mxx, x.second);
}

build(1, 1, mxx);

for(int i = 0; i < m; i++)
{
int l = qj[i].first, r = qj[i].second;
modify(1, l, r, 1);
}

LL ans = 0;

for(int i = 0; i < m; i++)
{
int l = qj[i].first, r = qj[i].second;
modify(1, l, r, -1);

int ri = n - l;
int le = n - r;

le = max(le, 1);
ri = min(ri, mxx);

LL sum = query(1, le, ri) % MOD;

ans = (ans + sum) % MOD;

modify(1, l, r, 1);
}

cout << ans << endl;
}


###### D：

void dfs(int u, int fa, int de)
{
dep[u] = de;

for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dfs(j, u, de + 1);
}
}

void solved()
{
memset(h, -1, sizeof h);

cin >> n;

for(int i = 2; i <= n; i++)
{
int x;
cin >> x;
}

for(int i = 1; i <= n; i++)
cin >> w[i];

dfs(1, -1, 1);

sort(dep + 1, dep + 1 + n, greater<int>());
sort(w + 1, w + 1 + n, greater<int>());

int ans = 0;

for(int i = 1; i <= n; i++)
{
ans += w[i] * dep[i];
}

cout << ans <<endl;
}

###### F：

void bfs(PII u, bool st[N][5], int dx[2], int dy[2])
{
queue<PII> q;
q.push(u);

while(q.size())
{
auto top = q.front();
q.pop();

int x = top.first, y = top.second;

for(int i = 0; i < 2; i++)
{
int zx = x + dx[i], zy = y + dy[i];
if(zx < 1 || zx > n || zy < 1 || zy > 3) continue;
if(st[zx][zy] || g[zx][zy])continue;
st[zx][zy] = true;

q.push({zx, zy});

}

}
}

void solved()
{

cin >> n >> k;

for(int i = 1; i <= n; i++) for(int j = 1; j <= 3; j++) st1[i][j] = st2[i][j] = g[i][j] = 0;

for(int i = 0; i < k; i++)
{
int x, y;
cin >> x >> y;
if(!g[x][y]) g[x][y] = true;
else g[x][y] = false;
}

st1[1][1] = true;
bfs({1, 1}, st1, dx1, dy1);
st2[n][3] = true;
bfs({n, 3}, st2, dx2, dy2);

int ans = 0;

if(!st1[n][3])
{
cout << 0 << endl;
return;
}
for(int i = 1; i <= n;i ++)
{
for(int j = 1; j <= 3; j++)
{
if(st1[i][j] && st2[i][j]) ans++;
}
}

cout << max(0, ans - 1) << endl;
}

###### H

void solved()
{

memset(cnt, 0, sizeof cnt);
memset(cf, 0, sizeof cf);

cin >> n;
int mxx = 0;

for(int i = 0; i < n; i++)
{
cin >> a[i];
cnt[a[i]] ++;
mxx = max(mxx, cnt[a[i]]);

}

for(int i = 1; i <= 100000; i++)
{
if(cnt[i])
{
cf[1]++;
cf[cnt[i] + 1]--;
}
}

for(int i = 1; i <= mxx; i++) cf[i] += cf[i - 1], g[i] = cf[i];
sort(cf + 1, cf + mxx, greater<int>());

int res = 0;

for(int i = 1; i <= mxx; i++)
res += cf[i];

for(int i = mxx; i <= n; i++) ans[i] = res;

for(int i = mxx - 1; i >= 1; i --)
{
res -= cf[i + 1];
res -= g[i + 1];
g[i] = g[i] - cf[i + 1];
ans[i] = res;
}

for(int i = 1; i <= n; i++) cout << ans[i] << '\n';

}


void solved()
{
memset(cnt, 0, sizeof cnt);
cin >> n;
int mxx = 0;

for(int i = 0; i < n; i++)
{
cin >> a[i];
cnt[a[i]] ++;
}

vector<int>num;
for(int i = 1; i <= 100000; i++) if(cnt[i]) num.push_back(cnt[i]);
int len = num.size();
sort(num.begin(), num.end());

int now = 0;
int lsum = 0;

for(int i = 1; i <= n; i++)
{
while(now != len && num[now] <= i)
{
lsum += num[now];
now++;
}

cout << lsum + (len - now) * (i - 1) << '\n';
}
}


###### J：

void solved()
{
int n;
cin >> n;
int sum = 0;

for(int i = 0; i < n; i++) cin >> a[i], sum += abs(a[i]);

int ans = 0;

for(int i = 0; i < n; i++)
{
ans += sum + n * abs(a[i]);
}

cout << ans << endl;

}

###### L：

void solved()
{
scanf("%lld%lld", &n, &p);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), a[i] %= p;

for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(i == j) continue;

cnt1[a[i] * a[j] % p]++;
cnt2[i][a[i] * a[j] % p] ++;
cnt2[j][a[i] * a[j] % p] ++;
}

for(int i = 0; i < p; i++)
{
int ans = 0;

for(int j = 1; j <= n; j++)
{
int x = (i - a[j] + p) % p;
ans += cnt1[x] - cnt2[j][x];
}

printf("%lld ", ans);
}

printf("\n");

}



##### 第一场

https://ac.nowcoder.com/acm/contest/46800#question

###### A：

void solved()
{
cin >> s + 1;

int A, B;
A = B = 0;

bool flag = false;

for(int i = 1; i <= 10; i++)
{
if(i % 2 != 0 && s[i] == '1')
A++;

if(i % 2 == 0 && s[i] == '1')
B++;

if(A > B)
{
if(A > B + (10 - i) / 2 + (i % 2))
{
flag = true;
cout << i << endl;
return;
}
}

if(B > A)
{
if(B > A + (10 - i) / 2)
{
flag = true;
cout << i << endl;
return;
}
}
}

if(!flag)
{
cout << -1 <<endl;
}
}

###### C：

void solved()
{
int n;
cin >> n;
int ans = 0;

for(int i = 0; i < n; i++)
{
cin >> a[i];
if(a[i]) ans++;
}

cout <<ans <<  endl;
}

###### F：

void solved()
{
cin >> n >> m;

for(int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;

for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
int pa = find(a), pb = find(b);
if(pa != pb)
{
p[pa] = pb;
cnt[pb] += cnt[pa];
}
}

int p = 0;
int ans = 0;
int ans2 = 0;

for(int i = 1; i <= n; i++)
{
int x, px;
cin >> x;

if(x)
{
px = find(i);
if(!bom[px])
{
p++;
ans += cnt[px] * cnt[px];
bom[px] = true;
}
}
if(i == find(i)) ans2 += cnt[i] * cnt[i];
}

if(!p)
{
cout << ans2 << endl;
}else if(p == 1) cout << ans <<endl;
else cout << 0 << endl;

}


###### G：

int f(int x)
{
return round(10 * sqrt(x));
}

void push_up(int u)
{
tr[u].sum = tr[u << 1]. sum + tr[u << 1 | 1].sum;
tr[u].flag = tr[u << 1].flag & tr[u << 1 | 1].flag;
}

void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, a[l], 0, 0};
return;
}

tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

push_up(u);
}

void modify(int u, int l, int r, int k)
{
int lr = (tr[u].r - tr[u].l + 1);
if(tr[u].flag) return;

if(tr[u].l == tr[u].r)
{

for(int i = 0; i < k; i++)
{
int last = tr[u].sum;
tr[u].sum = f(tr[u].sum);
if(last == tr[u].sum)
{
tr[u].flag = true;
break;
}
}
}else
{
int mid = tr[u].r + tr[u].l >> 1;

if(mid >= l) modify(u << 1, l, r, k);
if(r > mid) modify(u << 1 | 1, l, r, k);
push_up(u);
}
}

void solved()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];

build(1, 1, n);

for(int i = 0; i < m; i++)
{
int op, l, r, k;
cin >> op;

if(op == 1)
{
cin >> l >> r >> k;
modify(1, l, r, k);
}else
{
cout << tr[1].sum << endl;
}
}
}


###### H:

void solved()
{
cin >> n;

int p1 = 0, p2 = 0;

for(int i = 0; i < n * n - 1; i++)
{
cin >> ss[i];

int np1 = 0, np2 = 0;

for(int j = 0; j < 4; j++)
{
if(ss[i][j] == '1') p1++;
else if(ss[i][j] == '2')p2++;
}
}

cout <<  p1 - p2 + 10<< endl;

}

###### K：

void solved()
{
int n, m;
cin >> n >> m;

string s = "";

if((n - 1) / 3 + 1 >= m)
{
cout << 0 << endl;
return;
}

for(int i = 0; i < n; i++)
s += '0';

int sum = 2;
int pos = 0 ;

for(int i = 0; i < n; i++)
{
sum++;
if(sum == 3) s[i] = '1', sum = 0, pos++;
if(pos == m)
break;
}

sum = 0;

for(int i = n  - 1; i >= 0; i--)
{
if(sum + pos == m) break;

if(s[i] == '0')
{
s[i] = '1';
sum++;
}
}

int ans = 0;
for(int i = 0; i < n; i++)
{
if(i + 2 == n) break;

int sum = 0;
for(int j = i; j < i + 3; j++)
{
if(s[j] == '1') sum++;
}

if(sum >= 2)
{
ans++;
}
}

cout << ans << endl;
}


void solved()
{
int n, m;
cin >> n >> m;

string s = "";

for(int i = 0; i < n; i++)
s += '0';

int sum = 2;
int pos = 0 ;

for(int i = 0; i < n; i++)
{
sum++;
if(sum == 3) s[i] = '1', sum = 0, pos++;
if(pos == m)
break;
}

sum = 0;

for(int i = n  - 1; i >= 0; i--)
{
if(sum + pos == m) break;

if(s[i] == '0')
{
s[i] = '1';
sum++;
}
}

int ans = 0;
for(int i = 0; i < n; i++)
{
if(i + 2 == n) break;

int sum = 0;
for(int j = i; j < i + 3; j++)
{
if(s[j] == '1') sum++;
}

if(sum >= 2)
{
ans++;
}
}

cout << ans << endl;
}

###### M：

void solved()
{
cin >> n >> m;

for(int i = 1; i <= n; i++)
{
for(int j = m; j >= 0; j--)
{
for(int k = 0; k <= m; k++)
{
if(j + k <= m)
f[i][j] = max(f[i][j], f[i - 1][j + k] + (k * 1.0 /(j + k)));
}
}
}

long double ans = 0;

for(int i = 0; i <= m; i++) ans = max(ans, f[n][i]);

printf("%.8llf",ans);
}


##### #843 div2

https://codeforces.com/contest/1775

###### A2:

1.a <=b , c <= b

2.b <= a, b <= c

A,数据范围小，统一看B做法

void solved()
{
string s;
cin >> s;

int pos = -1;

for(int i = 0; i < s.size(); i++)
{
if(s[i] == 'a' && i != 0 && i != s.size() - 1)
{
pos = i;
break;
}
}

if(pos != -1)
{
for(int i = 0; i < pos; i++) cout << s[i]; cout << " a " << " ";
for(int i = pos + 1; i < s.size(); i++) cout << s[i];
cout << endl;
}else
{
cout << s[0] << " ";
for(int i = 1; i < s.size() - 1; i++) cout << s[i];
cout << " " << s[s.size() - 1];
cout << endl;
}
}

###### B：

void solved()
{
map<int,int>cnt;

int n;
cin >>  n;
int mxx = 0;
for(int i = 0; i < n; i++)
{
int k;
cin >> k;
w[i].clear();
for(int j = 0; j < k; j++)
{
int x;
cin >> x;
w[i].push_back(x);
cnt[x]++;
}
}

for(int i = 0; i < n; i++)
{
bool flag = false;

for(int j = 0; j < w[i].size(); j++)
{
int x = w[i][j];

if(cnt[x] == 1)
{
flag = true;
}
}

if(!flag)
{
cout << "YES" << endl;
return ;
}
}

cout << "NO" << endl;

}

###### C：

1.n - 0， x - 1

2.n - 0, x - 0

3.n - 1, x - 1

4.n - 1, x - 0,

1，2 两种情况不需要特别考虑但对于 3， 4 有特别要求。

void solved()
{
int n, m;
cin >> n >> m;

vector<int> wn, wm;

int n1  = n, m1 = m;

if(n1 == 0) wn.push_back(0);
if(m1 == 0) wm.push_back(0);

while(n1) wn.push_back(n1 % 2), n1 /= 2;
while(m1) wm.push_back(m1 % 2), m1 /= 2;

if(wm.size() > wn.size())
{
cout << -1 << endl;
return;
}

int ln = wn.size(), lm = wm.size();

for(int i = 0; i < ln - lm;i ++)
{
wm.push_back(0);
}

int ans = 0;
bool flag = false;
int pos00 = wm.size();
bool h10 = false;
bool h00 = false;
int pos11 = 1e9;

for(int i = wn.size() - 1; i >= 0; i--)
{
if(wn[i] == 0 && wm[i] == 1)
{
cout << -1 << endl;
return;
}

if(wn[i] == 1 && wm[i] == 0)
{
h10 = true;

if(!h00)
{
h00 = true;
ans += 1ll << (pos00);

if(pos00 >= pos11)
{
cout << -1 << endl;
return;
}
}
}

if(wn[i] == 0 && wm[i] == 0)
{
pos00 = i;
}

if(wn[i] == 1 && wm[i] == 1)
{
if(h10)
{
cout << -1 << endl;
return;
}

pos11 = i;

ans += 1ll << i;

}
}

cout << ans << endl;
}

###### D：

int bfs()
{
deque<int>q;
q.push_back(start);

memset(dist, 0x3f,sizeof dist), memset(vis, 0, sizeof vis);
dist[start] = 0;

while(q.size())
{
int top = q.front();
q.pop_front();
if(vis[top]) continue;
vis[top] = true;

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

if(ww == 0)
{
if(dist[j] > dist[top])
{
dist[j] = dist[top];
pre[j] = top;
q.push_front(j);
}
}else
{
if(dist[j] > dist[top] + 1)
{
dist[j] = dist[top] + 1;
pre[j] = top;
q.push_back(j);
}
}

}
}

if(dist[edd] >= 0x3f3f3f3f / 2) return -1;
return dist[edd];
}

void solved()
{
idx = 0;
cin >> n;
memset(h, -1, sizeof h);

int mxx = 0;
for(int i = 1; i <= n; i++) cin >> a[i], mxx = max(mxx, a[i]);
cin >> start >> edd;

map<PII, int> mp;

if(start == edd)
{
cout << 1 << endl;
cout << edd <<endl;
return;
}

if(a[start] == a[edd])
{
if(a[start] == 1)
{
cout << -1 << endl;
return;
}

cout << 2 << endl;
cout << start << " " << edd << endl;
return;

}

for(int i = 1; i <= n; i++)
{
for(int j = a[i]; j >= 2; j /= st[j])
{

if(mp[{i, st[j]}]) continue;

mp[{i, st[j]}] = 1;
}
}

int ans = bfs();

if(ans == -1)
{
cout << -1 << endl;
}else
{

vector<int>res;
int now = edd;

while(now != start)
{
if(now <= n) res.push_back(now);
now = pre[now];
}

res.push_back(start);
cout << res.size() << endl;
for(int i = res.size() - 1; i >= 0; i--) cout << res[i] << " ";
cout << endl;

}
}


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;

struct Node
{
int l, r;
LL sum;
}tr[N * 4];

int n, m;
LL a[N];

void push_up(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, a[l]};
return;
}

tr[u] = {l, r};

int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

push_up(u);
}

void modify(int u, int l, int r)
{

if(tr[u].r - tr[u].l + 1 == tr[u].sum)
{
return;
}

// cout << tr[u].l << " " << tr[u].r << endl;

if(tr[u].l == tr[u].r && tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum = sqrt(tr[u].sum);
return;
}

int mid = tr[u].l + tr[u].r >> 1;

if(mid >= l) modify(u << 1, l, r);
if(r > mid) modify(u << 1 | 1, l, r);

push_up(u);
}

LL query(int u, int l, int r)
{

// cout << tr[u].l << " " <<tr[u].r << endl;

if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum;
}

LL ans = 0;
int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) ans += query(u << 1, l, r);
if(r > mid) ans += query(u << 1 | 1, l, r);

return ans;
}

int main()
{
ios::sync_with_stdio(false);

int T = 1;

while(cin >> n)
{
cout << "Case #" << T ++ << ":" <<endl;

for(int i = 1; i <= n; i++) cin >> a[i];

build(1, 1, n);

cin >> m;
for(int i = 0; i < m; i++)
{
LL op, l, r;
cin >> op >> l >> r;

if(l > r) swap(l, r);
if(op == 0)
{
modify(1, l, r);
}
else
{
cout << query(1, l, r) << endl;
}
}
cout << endl;
}

}



#include<bits/stdc++.h>
using namespace std;
const int N = 80000 + 10;
int n;

struct Node
{
int l, r;
int col;
int lazy;
}tr[N * 4];

void push_down(int u)
{
Node &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];

if(root.lazy != -1)
{
l.col = r.col = root.lazy;
l.lazy = r.lazy = root.lazy;
root.lazy = -1;
}
}

void build(int u, int l, int r)
{
if(l == r)
{
tr[u] = {l, r, -1, -1};
return;
}

tr[u] = {l, r, -1, -1};

int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int w)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].col = w;
tr[u].lazy = w;
return;
}else
{
push_down(u);

int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) modify(u << 1, l, r, w);
if(r > mid) modify(u << 1 | 1, l, r, w);
}

}

int query(int u, int l, int r)
{
if(tr[u].l == tr[u].r)
{
return tr[u].col;
}

push_down(u);

int mid = tr[u].l + tr[u].r >> 1;

if(l <= mid) return query(u << 1, l, r);
if(r > mid) return query(u << 1 | 1, l, r);

return -1;
}

int main()
{
while(cin >> n)
{
build(1, 1, 80001);

map<int, int> sum;

int mxx = 0;

for(int i = 0; i < n; i++)
{
int w, l, r;
cin >> l >> r >> w;
l++, r++;

mxx = max(mxx, r);
modify(1, l, r - 1, w);
}

int col =  query(1, 1, 1);

if(col != -1)
sum[col]++;

for(int i = 1; i < mxx; i++)
{
int x = query(1, i, i);
if(x != col && x != -1) sum[x]++, col = x;
}

for(auto x : sum)
{
cout << x.first << " " << x.second << endl;
}

cout << endl;

}

return 0;
}


##### Hello 2023

https://codeforces.com/contest/1779

###### A:

void solved()
{
cin  >> n;
string s;
cin >> s;

bool flag = false;

bool pl, pr;
pl = pr = false;

for(int i = 0; i < n; i++)
{
if(pr == true && pl == false && s[i] == 'L')
{
cout << 0 << endl;
flag = true;
return;
}

if(s[i] == 'L') pl = true;
else pr = true;
}

for(int i = 0; i < n - 1; i++)
{

if(s[i] == 'L' && s[i + 1] == 'R')
{
cout << i  + 1 << endl;
flag = true;
return;
}
}

if(flag == false)
{
cout << -1 << endl;
}

}

###### B：

a1 + a2 = a1 + a2 + a3 +.... an

0 = a3 + … an;

a3 + a5 +.. a n-1 = a4 + a6 + .. an

a3 = (a4 - a5) + (a6- a7) + (an - 1 - an)

void solved()
{
cin >> n;

if(n == 3)
{
cout << "NO" << endl;
return;
}

cout << "YES" <<endl;

if(n % 2 == 0)
{
for(int i = 1; i <= n; i++)
{
if(i % 2 != 0)
cout << 1 << " ";
else cout << -1 << " ";
}

cout << endl;
}else
{
int x =  n / 2 - 1;
int y = - x - 1;

for(int i = 1; i <= n; i++)
{
if(i & 1) cout << x <<" ";
else cout << y << " ";
}

cout << endl;

}
}


###### C：

1.对于 m来说，要满足 sm是最小值，那么 m 必须 <= 0, 否则，再 s[m - 1] + a[m] > s[m]

2.对于 1 - m -1 来说，题目给出的不等式变换一下 0 >= ak + 1.... + a[m - 1]

3.对于 m + 1 - n 来说 am + 1… a[k] >= 0, 满足 m + 1 - k 的前缀 >= 0

void solved()
{
cin >> n >> m;

for(int i = 1; i <= n; i++) cin >> a[i];

priority_queue<int> q;
int sum, ans = 0;

if(n == 1)
{
cout << 0 << endl;
return ;
}

if(a[m] > 0 && m > 1) ans++, a[m] *= -1;
sum += a[m];

for(int i = m - 1; i >= 2; i --)
{
sum += a[i];
q.push(a[i]);

while(sum > 0)
{
int x = q.top();
q.pop();
x*=-1;
sum += 2 * x;
ans++;
}
}

sum  = 0;

priority_queue<int, vector<int>, greater<int>> q2;

for(int i = m + 1; i <= n; i++)
{
sum += a[i];
q2.push(a[i]);

while(sum < 0)
{
int x= q2.top();
q2.pop();
x*=-1;
sum += 2 * x;
ans++;
}
}

cout << ans << endl;

}


###### D：

void init()
{
for(int j = 0; j < M; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
{
if(!j) f[i][j] = b[i];
else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}

int query(int l, int r)
{
int len = r - l + 1;

int k = log(len) / log(2);

return(max(f[l][k], f[r - (1 << k) + 1][k]));
}

void solved()
{
cnt.clear();

cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
cin>> m;
for(int i = 1; i <= m; i++) cin >> w[i], cnt[w[i]]++;

for(int i = 1; i <= n; i++)
{
if(a[i] < b[i])
{
cout << "NO" << endl;
return;
}
}

init();
map<int, vector<int>>hs;

for(int i = 1; i <= n; i++) if(b[i] != a[i])hs[b[i]].push_back(i);

for(auto x : hs)
{
int now = x.first;
vector<int> pos = x.second;

int ans = 1;

int l, r;
if(pos.size() != 1)
l = pos[0], r = pos[1];
for(int i = 0; i < pos.size() - 1; i++)
{
r = pos[i + 1];

if(query(l, r) > now)
l = pos[i + 1], ans++;
}

if(cnt[now] < ans)
{

cout << "NO" << endl;
return;
}

}

cout << "YES" << endl;

}


#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = 18;

int n, m;
int f[N][M];
int a[N];

int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];

for(int j = 0; j < M; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
{
if(!j) f[i][j] = a[i];
else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}

cin >> m;

for(int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
int len = r - l + 1;

int k = log(len) / log(2);

cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
int tr[N][26], idx;
int id[210], f[N];
char str[N];
int q[N], ne[N];
int n;

void insert(int x)
{
int p = 0;

for(int i = 0; str[i]; i++)
{
int t = str[i] - 'a';

if(!tr[p][t]) tr[p][t] = ++ idx;
p = tr[p][t];

f[p]++;
}

id[x] = p;
}

void build()
{
int hh = 0, tt = -1;

for(int i = 0; i < 26; i++) if(tr[0][i]) q[++tt] = tr[0][i];

while(hh <= tt)
{
int t = q[hh++];

for(int i = 0; i < 26; i++)
{
int j = tr[t][i];

if(!j) tr[t][i] = tr[ne[t]][i];
else
{
ne[j] = tr[ne[t]][i];
q[++tt] = j;
}
}
}
}

int main()
{
cin >> n;

for(int i = 1; i <= n; i++) cin >> str, insert(i);

build();

for(int i = idx - 1; i >= 0; i--) f[ne[q[i]]] += f[q[i]];

for(int i = 1; i <= n; i++) cout << f[id[i]] << endl;
}