歪嗯哦唉 代码补全计划
题解大概在 根号数据结构练习 里
- P3604 美好的每一天
好像不算 Ynoi 题，不过都素晴日了就写一下吧。
神秘啊，hydro ide getchar() 都没问题，但是洛谷全 WA，改成 cin 就过了。
#include <bits/stdc++.h>
#define Maxn 60005
#define Nep(i, l, r) for(int i = l; i != r; ++ i)
#define Rep(i, l, r) for(int i = l; i <= r; ++ i)
#define rep(i, l, r) for(int i = l; i < r; ++ i)
#define Lep(i, l, r) for(int i = l; i >= r; -- i)
#define lep(i, l, r) for(int i = l; i > r; -- i)
#define ll long long
#define ull unsigned long long
//#define int long long
int read() {
int x = 1, res = 0, ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') x = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return x * res;
}
int n, m, B = 250;
int L[Maxn], R[Maxn], id[Maxn];
int s[Maxn], t[1 << 26];
int ans[Maxn], res;
int l = 0, r = -1;
bool cmp(int x, int y) {
if(L[x] / B == L[y] / B) return R[x] < R[y];
return L[x] < L[y];
}
void add(int x) {
for(int i = 0; i < 26; ++ i)
res += t[s[x] ^ (1 << i)];
res += t[s[x]];
t[s[x]] ++;
}
void del(int x) {
for(int i = 0; i < 26; ++ i)
res -= t[s[x] ^ (1 << i)];
t[s[x]] --;
res -= t[s[x]];
}
signed main() {
n = read(), m = read();
Rep(i, 1, n) {
char c;
std :: cin >> c;
s[i] = s[i - 1] ^ (1 << c - 'a');
}
Rep(i, 1, m) L[i] = read() - 1, R[i] = read(), id[i] = i;
std :: sort(id + 1, id + m + 1, cmp);
Rep(i, 1, m) {
int ql = L[id[i]], qr = R[id[i]];
while(ql < l) add(-- l);
while(qr > r) add(++ r);
while(ql > l) del(l ++);
while(qr < r) del(r --);
ans[id[i]] = res;
}
Rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}- P5356 [Ynoi Easy Round 2017] 由乃打扑克
老早之前就写过了，朋友帮忙卡的常，就不重构了。
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define Maxn 100005
#define Maxlen 320
#define inf 1000000000
int n, m, a[Maxn], b[Maxn], belong[Maxn], L[Maxlen], R[Maxlen], tag[Maxlen], len, tot, ans, l, r, mid;
int *tmp;
#define min(a, b) ( a < b ? a : b );
inline void rebuild(int x) {
for(register int i = L[x]; i <= R[x]; ++ i) a[i] = b[i];
std :: sort(a + L[x], a + R[x] + 1);
}
inline void upd(const int & l, const int & r, const int & k) {
if(belong[l] == belong[r]) {
for(register int i = l; i <= r; ++ i) b[i] += k;
rebuild(belong[l]);
return;
}
register int i;
for(i = l; i < L[belong[l] + 1]; ++ i) b[i] += k ;
for(i = belong[l] + 1; i < belong[r]; ++ i) tag[i] += k;
for(i = L[belong[r]]; i <= r; ++ i) b[i] += k;
rebuild(belong[l]), rebuild(belong[r]);
return ;
}
inline int ranking(const int & l, const int & r, const int & val) {
int ans = 0;
if(belong[l] == belong[r]) {
for(register int i = l; i <= r; ++ i) (b[i] + tag[belong[i]] <= val && ++ ans);
return ans;
}
register int i;
for(i = l; i < L[belong[l] + 1]; ++ i) (b[i] + tag[belong[l]] <= val && ++ ans);
for(i = belong[l] + 1; i < belong[r]; ++ i) {
if(a[L[i]] > val - tag[i]) ;///here
else if(a[R[i]] <= val - tag[i]) ans += R[i] - L[i] + 1;///here
else ans += (tmp = (std :: upper_bound(a + L[i], a + R[i] + 1, val - tag[i]))) == (a + R[i] + 1) ? R[i] - L[i] + 1 : tmp - (a + L[i]);
}
for(i = L[belong[r]]; i <= r; ++ i) (b[i] + tag[belong[r]] <= val && ++ ans);
return ans;
}
inline int findkth(const int & bg, const int & ed, const int & k) {
if(k < 1) return -1;
if(k > ed - bg + 1) return -1;
register int ans = -1, l = - inf, r = inf;
while(l <= r)
ranking(bg, ed, mid = l + r >> 1) >= k ? ans = mid, r = mid - 1 : l = mid + 1;
return ans;
}
struct IO {
static const int S=1<<21;
char buf[S],*p1,*p2;
int st[105],Top;
~IO() {
clear();
}
inline void clear() {
fwrite(buf,1,Top,stdout);
Top=0;
}
inline void pc(const char c) {
Top==S&&(clear(),0);
buf[Top++]=c;
}
inline char gc() {
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline IO&operator >> (char&x) {
while(x=gc(),x==' '||x=='\n'||x=='r');
return *this;
}
template<typename T>inline IO&operator >> (T&x) {
x=0;
bool f=0;
char ch=gc();
while(ch<'0'||ch>'9') {
if(ch=='-') f^=1;
ch=gc();
}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;
return *this;
}
inline IO&operator << (const char c) {
pc(c);
return *this;
}
template<typename T>inline IO&operator << (T x) {
if(x<0) pc('-'),x=-x;
do {
st[++st[0]]=x%10,x/=10;
} while(x);
while(st[0]) pc('0'+st[st[0]--]);
return *this;
}
} fin,fout;
int main() {
fin >> n >> m;
len = (int)sqrt(n);
tot = (n - 1) / len + 1;
for(int i = 1; i <= tot; ++ i) {
L[i] = R[i - 1] + 1, R[i] = min(len * i, n);
for(int j = L[i]; j <= R[i]; ++ j) fin >> a[j], belong[j] = i, b[j] = a[j];
std :: sort(a + L[i], a + R[i] + 1);
}
int opt, l, r, k;
while(m --) {
fin >> opt >> l >> r >> k;
if(opt == 1) fout << findkth(l, r, k) << '\n';
else upd(l, r, k);
}
return 0;
}- P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I
是的我是由乃单推人。
很深刻的题，逆序对强制在线。
预处理做好查询内只有归并是根号的，其他都是
我还没看到有我同款实现的题解，事实上预处理也可以根号平衡做，不过貌似常数更大
//你很牛吗？放下你的身段！
#include <bits/stdc++.h>
#define Maxn 100005
#define Nep(i, l, r) for(register int i(l), _(r); i != _; ++ i)
#define Rep(i, l, r) for(register int i(l), _(r); i <= _; ++ i)
#define rep(i, l, r) for(register int i(l), _(r); i < _; ++ i)
#define Lep(i, l, r) for(register int i(l), _(r); i >= _; -- i)
#define lep(i, l, r) for(register int i(l), _(r); i > _; -- i)
#define ll long long
#define ull unsigned long long
//#define int long long
namespace FastIO{
static char buf[10000000],*p1=buf,*p2=buf;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++;
inline int read() {int res=0,w=0; char c=gc; while (!isdigit(c)) c=gc; while (isdigit(c)) res=(res<<1)+(res<<3)+(c^48),c=gc; if (w) res=-res; return res;}
//inline void write(int x) {static int sta[35],top=0; do {sta[top++]=x%10,x/=10;}while (x); while (top) putchar(sta[--top]+48); putchar('\n');}
inline void write(long long x) {static int sta[50],top=0; do {sta[top++]=x%10,x/=10;}while (x); while (top) putchar(sta[--top]+48); putchar('\n');}
};
using namespace FastIO;
const int B = 500, Maxt = Maxn / B + 5;
int a[Maxn], bcnt, n, m;
int bel[Maxn];
int L[Maxt], R[Maxt];
ll res[Maxt][Maxt];
int da[Maxn];
int ov[Maxn];
int dov[Maxn];
int p[Maxn][Maxt];
ll pre[Maxt][Maxn];
ll d[Maxn];
int st[Maxn], sp[Maxt];
ll rs[Maxn];
struct bit {
int s[Maxn];
void add(int x) {
for(; x <= n; x += x & -x) s[x] ++;
}
int query(int x) {
int res(0);
for(; x; x -= x & -x) res += s[x];
return res;
}
}T;
signed main() {
//reopen("1.in", "r", stdin);
n = read(), m = read();
Rep(i, 1, n) bel[i] = (i - 1) / B + 1;
Rep(i, 1, bel[n]) L[i] = R[i - 1] + 1, R[i] = L[i] + B - 1;
bcnt = bel[n], R[bcnt] = n;
Rep(i, 1, n) a[i] = read(), ov[i] = a[i], da[a[i]] = i;
Rep(b, 1, bcnt) std :: sort(ov + L[b], ov + R[b] + 1);
Rep(i, 1, n) dov[i] = da[ov[i]], T.add(a[i]), d[i] = d[i - 1] + T.query(a[i] - 1), p[a[i]][bel[i]] ++;
Rep(b, 1, bcnt) Rep(i, 1, n) p[i][b] += p[i - 1][b] + p[i][b - 1] - p[i - 1][b - 1];
Rep(i, 1, n) Rep(b, 1, bcnt) pre[b][i] = pre[b][i - 1] + p[a[i] - 1][b];
Rep(b, 1, bcnt) res[b][b] = (R[b] - L[b]) * (R[b] - L[b] + 1) / 2 - d[R[b]] + d[L[b] - 1] + pre[b - 1][R[b]] - pre[b - 1][L[b] - 1];
Rep(i, 1, n) rs[i] = i - L[bel[i]] - d[i] + d[i - 1] + pre[bel[i] - 1][i] - pre[bel[i] - 1][i - 1];
Rep(i, 1, n) if(L[bel[i]] ^ i) rs[i] += rs[i - 1];
Lep(l, bcnt, 1) Rep(r, l + 1, bcnt) {
res[l][r] += res[l + 1][r] + res[l][l],
res[l][r] += pre[r][R[l]] - pre[r][L[l] - 1],
res[l][r] -= pre[l][R[l]] - pre[l][L[l] - 1];
}
ll las(0);
Rep(q, 1, m) {
ll ql(read()), qr(read());
const int l(ql ^ las), r(qr ^ las);
if(bel[l] == bel[r]) {
ll ans = rs[r];
if(L[bel[l]] ^ l) ans -= rs[l - 1];
register int lc(L[bel[l]]), rc(L[bel[l]]), len(r - L[bel[l]] + 1);
register int rcnt(0);
Rep(i, 1, len) {
const int RbL(R[bel[l]]);
while(dov[lc] >= l && lc <= RbL) lc ++;
while((dov[rc] < l || dov[rc] > r) && rc <= RbL) rc ++;
if(lc > RbL) break;
if(rc > RbL) {
ans -= 1LL * (len - i + 1) * rcnt;
break;
}
if(ov[lc] < ov[rc]) lc ++, ans -= rcnt;
else rc ++, rcnt ++;
}
write(ans), las = ans;
continue;
}
const int bL = bel[l], bR = bel[r];
ll ans = res[bL + 1][bR - 1];
const int len = r - L[bR] + 2 + R[bL] - l;
int lc = L[bL], rc = L[bR], rcnt = 0;
Rep(i, 1, len) {
const int RbL = R[bL], RbR = R[bR];
while(dov[lc] < l && lc <= RbL) lc ++;
while(dov[rc] > r && rc <= RbR) rc ++;
if(lc > RbL) break;
if(rc > RbR) {
ans += 1LL * (len - i + 1) * rcnt;
break;
}
if(ov[lc] < ov[rc]) lc ++, ans += rcnt;
else rc ++, rcnt ++;
}
ans += pre[bR - 1][R[bL]] - pre[bR - 1][l - 1],
ans -= d[R[bL]] - d[l - 1],
ans += 1LL * (L[bR] + r) * (r - L[bR] + 1) / 2,
ans -= 1LL * (R[bL] + 1) * (r - L[bR] + 1),
ans -= d[r] - d[L[bR] - 1],
ans += pre[bL][r] - pre[bL][L[bR] - 1],
write(ans), las = ans;
}
return 0;
}- P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III
代码没什么难度，确实是小 trick 题。
为啥子不做 II 呢，因为 II 确实是很板的题，不着急。
//你很牛吗？放下你的身段！
#include <bits/stdc++.h>
#define Maxn 500005
#define Nep(i, l, r) for(int i = l; i != r; ++ i)
#define Rep(i, l, r) for(int i = l; i <= r; ++ i)
#define rep(i, l, r) for(int i = l; i < r; ++ i)
#define Lep(i, l, r) for(int i = l; i >= r; -- i)
#define lep(i, l, r) for(int i = l; i > r; -- i)
#define ll long long
#define ull unsigned long long
//#define int long long
const int B = 500, Maxt = Maxn / B + 5;
int L[Maxt], R[Maxt], bcnt, bel[Maxn];
int c[Maxn], ans[Maxt][Maxt], o[Maxn], a[Maxn];
std :: vector <int> G[Maxn];
int read() {
int x = 1, res = 0, ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') x = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return x * res;
}
signed main() {
int n = read(), m = read();
Rep(i, 1, n) bel[i] = (i - 1) / B + 1; bcnt = bel[n];
Rep(i, 1, bcnt) L[i] = R[i - 1] + 1, R[i] = R[i - 1] + B;
Rep(i, 1, n) a[i] = read(), G[a[i]].push_back(i), o[i] = G[a[i]].size() - 1;
R[bcnt] = n;
Rep(l, 1, bcnt) {
int res = 0;
rep(i, 1, Maxn) c[i] = 0;
Rep(r, l, bcnt) {
Rep(i, L[r], R[r]) res = std :: max(res, ++ c[a[i]]);
ans[l][r] = res;
}
}
rep(i, 1, Maxn) c[i] = 0;
int las = 0;
Rep(q, 1, m) {
int l = read() ^ las, r = read() ^ las;
if(bel[l] == bel[r]) {
int res = 0;
Rep(i, l, r) res = std :: max(res, ++ c[a[i]]);
Rep(i, l, r) -- c[a[i]];
printf("%d\n", res), las = res;
continue;
}
int res = ans[bel[l] + 1][bel[r] - 1];
Rep(i, l, R[bel[l]]) while(o[i] + res < G[a[i]].size() && G[a[i]][o[i] + res] <= r) res ++;
Rep(i, L[bel[r]], r) while(o[i] - res >= 0 && G[a[i]][o[i] - res] >= l) res ++;
printf("%d\n", res), las = res;
}
return 0;
}