专栏文章

歪嗯哦唉 代码补全计划

vvvautedSN第一魔怔人
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipin1ar
此快照首次捕获于
2025/12/03 12:37
3 个月前
此快照最后确认于
2025/12/03 12:37
3 个月前
查看原文
题解大概在 根号数据结构练习 里
  • P3604 美好的每一天
好像不算 Ynoi 题，不过都素晴日了就写一下吧。
神秘啊，hydro ide getchar() 都没问题，但是洛谷全 WA，改成 cin 就过了。
CPP
#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] 由乃打扑克
老早之前就写过了，朋友帮忙卡的常，就不重构了。
CPP
#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
是的我是由乃单推人。
很深刻的题，逆序对强制在线。
预处理做好查询内只有归并是根号的，其他都是 O(1)O(1)，算是很优秀的实现了。
我还没看到有我同款实现的题解，事实上预处理也可以根号平衡做，不过貌似常数更大
CPP
//你很牛吗？放下你的身段！
#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 确实是很板的题，不着急。
CPP
//你很牛吗？放下你的身段！
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...