Who am I?

張集貴
pr3pony
i use arch btw

outline

選手之路
DEBUG
基本演算法：複雜度，C++ STL，枚舉，二分，排序
DS
圖論

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN (1000 + 42)
#define R first
#define C second
using namespace std;
typedef pair<int, int> pii;
char g[MAXN][MAXN];
int b[MAXN][MAXN];
int w[MAXN][MAXN];
int R, C;
pii d[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

pii walk(pii a, pii b) {
    a.R += b.R;
    a.C += b.C;
    return a;
}

bool inrange(pii p) {
    return 0 <= p.R && p.R < R && 0 <= p.C && p.C < C;
}

bool block(pii p) {
    return g[p.R][p.C] == '#';
}

int& burn_t(pii p) {
    return b[p.R][p.C];
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        queue<pii> f, j;
        scanf("%d%d ", &R, &C);
        for (int r = 0; r < R; r++)
            memset(b[r], -1, C * sizeof(int));
        for (int r = 0; r < R; r++)
            memset(w[r], -1, C * sizeof(int));
        for (int r = 0; r < R; r++) {
            fgets(g[r], sizeof(g[r]), stdin);
            for (int c = 0; c < C; c++)
                switch (g[r][c]) {
                    case 'F':
                        b[r][c] = 0;
                        f.push({r, c});
                        break;
                    case 'J':
                        w[r][c] = 0;
                        j.push({r, c});
                        break;
                }
        }
        while (!f.empty()) {
            pii p = f.front();
            f.pop();
            int t = burn_t(p) + 1;
            for (pii x : d) {
                pii n = walk(p, x);
                if (inrange(n) && !block(n) && burn_t(n) == -1) {
                    burn_t(n) = t;
                    f.push(n);
                }
            }
        }
        int fin = -1;
        while (!j.empty()) {
            pii p = j.front();
            j.pop();
            int t = w[p.R][p.C] + 1;
            for (pii x : d) {
                pii n = walk(p, x);
                if (inrange(n)) {
                    if (!block(n) && (burn_t(n) > t || burn_t(n) == -1) && w[n.R][n.C] == -1) {
                        w[n.R][n.C] = t;
                        j.push(n);
                    }
                } else {
                    fin = t;
                    goto output;
                }
            }
        }
output:
        if (fin != -1)
            printf("%d\n", fin);
        else
            puts("IMPOSSIBLE");
    }
}

TIOJ 1827: 區間 rank + 二分搜

 #include <bits/stdc++.h>
using namespace std;
// nichijou
#define REP(i,a,b) for (int i = (a), __e = (b); i < __e; ++i)
#define RP(i,n) REP(i,0,n)
#define PER(i,s,e) for (int i = (s) - 1, __e = (e); i >= __e; --i)
#define PR(i,n) PER(i,n,0)
#define REP1(i,a,b) for (int i = (a), __e = (b); i <= __e; ++i)
#define RP1(i,n) REP1(i,1,n)
#define PER1(i,s,e) for (int i = (s), __e = (e); i >= __e; --i)
#define PR1(i,n) PER1(i,n,1)
#define DO(n) REP(__i,0,n)
template<typename T>
void cmax(T & a, T b) {a = max(a, b);}
template<typename T>
void cmin(T & a, T b) {a = min(a, b);}
 
// data type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
 
// STL container
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()
#define CLR(a) a.clear()
#define BK(a) (a.back())
#define FT(a) (a.front())
#define DB(a) a.pop_back()
#define DF(a) a.pop_front()
#define PB push_back
#define EB emplace_back
 
/* Reading input is now 20% cooler! */
bool RD(void) {return true;}
template<typename T>
bool RD(T & a)
{
	int c;
	while (!isdigit(c = getchar()));
	a = c&15;
    while (isdigit(c = getchar()))
        a = 10 * a + (c & 15);
	return 1;
}
bool RD(double & a) {return scanf("%lf", &a) == 1;}
bool RD(char & a) {return scanf(" %c", &a) == 1;}
bool RD(char * a) {return scanf("%s", a) == 1;}
template<typename T, typename ... TT>
bool RD(T & a, TT & ...  b) {return RD(a) && RD(b...);}
 
/* Do princesses dream of magic sheep? */
#define RI(a) int a; RD(a)
#define RII(a,b) RI(a); RI(b)
#define RIII(a,b,c) RI(a); RII(b,c)
#define RIIII(a,b,c,d) RI(a); RIII(b,c,d)
 
/* For it's time for you to fulfill your output. */
void PT(const char * a) {fputs(a, stdout);}
void PT(char * a) {fputs(a, stdout);}
template<typename T>
void PT(const T a)
{
	static const int maxd = 25;
	static char d[maxd];
	int i = maxd - 1;
	T t = a;
    do {
        d[--i] = (t % 10) | 48;
    } while (t /= 10);
	PT(d + i);
}
void PT(const double a) {printf("%.16f", a);}
void PT(const char a) {putchar(a);}
 
/* The line will last forever! */
void PL(void) {PT('\n');}
template<typename T, typename ... TT>
void PL(const T a, const TT ...  b) {PT(a); if (sizeof...(b)) PT(' '); PL(b...);}
 
/* Good Luck && Have Fun ! */
const int N = 1e5 + 87;
const int D = __lg(N)+1;
struct node
{
	int s;
	node*l,*r;
} mem[N*D*2];
node * rt[N],* ptr=mem;
node * add(node * t,int l,int r,int i)
{
	t=t?new(ptr++) node(*t):new(ptr++) node();
	++t->s;
	if (r-l==1)
		return t;
	int m=l+((r-l)>>1);
	if (i<m)
		t->l=add(t->l,l,m,i);
	else
		t->r=add(t->r,m,r,i);
	return t;
}
int qry(node*t,int l,int r,int i,int s=0)
{
	if (!t)
		return s;
	if (r==i+1)
		return s+t->s;
	int m=l+((r-l)>>1);
	if (i<m)
		return qry(t->l,l,m,i,s);
	return qry(t->r,m,r,i,(t->l?t->l->s:0) + s);
}
int main()
{
	RII(n,m);
	RP1(i,n) {
		RI(b);
		rt[i] = add(rt[i-1],1,n+1,b);
	}
	DO(m) {
		RII(p,k);
		++p;
		int lo = 1, hi = n;
		while (lo <= hi) {
			int mi=(lo+hi)>>1;
			if (qry(rt[min(p+mi,n)],1,n+1,mi) - qry(rt[max(p-mi-1,0)],1,n+1,mi) >= k)
				hi = mi - 1;
			else
				lo = mi + 1;
		}
		PL(lo);
	}
}

 #include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define F first
#define S second
/* I DUCK HORSE */
const int N = 5e5 + 87;
struct hp
{
    size_t operator () (const pii & x) const
    {
        return hash<long long>()(((long long)x.F)<<20 | x.S);
    }
};
unordered_map<pii,pii,hp> la;
vector<pii> t[N*4];
int p[N],sz[N],cc,tp;
pair<int,int> h[N];
 
void jizz(int o,int l,int r,int i,int j, pii x)
{
    if (i <= l && r <= j) {
        t[o].push_back(x);
        return;
    }
    int m=(l+r)>>1;
    if (i < m)
        jizz(o+o+1,l,m,i,j,x);
    if (j > m)
        jizz(o+o+2,m,r,i,j,x);
}
int find(int x) {return x == p[x] ? x : find(p[x]);}
void gao(int o,int l,int r)
{
//cout<<'['<<l<<','<<r<<']'<<'\n';
    int otp = tp, occ = cc;
    for (const auto & x : t[o]) {
//cout<<x.F<<','<<x.S<<'\n';
        int a = find(x.F), b = find(x.S);
        if (a == b)
            continue;
        if (sz[a] > sz[b])
            swap(a,b);
        h[tp++] = {a,p[a]};
        p[a]=b;
        sz[b]+=sz[a];
        --cc;
    }
    t[o].clear();
 
    if (r-l == 1) {
        cout << cc << '\n';
    } else {
        int m=l+((r-l)>>1);
        gao(o+o+1,l,m);
        gao(o+o+2,m,r);
    }
    while (tp > otp) {
        --tp;
        int a = h[tp].F;
        sz[p[a]] -= sz[a];
        p[a] = h[tp].S;
    }
    cc = occ;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    for (int i = 0; i < N; ++i)
        p[i] = i;
    fill_n(sz,N,1);
 
    int T;
    cin>>T;
    while (T--) {
        la.clear();
        int n,m,q;
        cin>>n>>m>>q;
        cc = n;
        for (int i = 0; i < m; ++i) {
            int u,v;
            cin>>u>>v;
            if (u>v)
                swap(u,v);
            pii x(u,v);
            auto it = la.find(x);
            if (it == la.end() || it->F != x)
                la.insert({x,{0,1}});
            else
                it->S.S++;
        }
        for (int i = 0; i < q; ++i) {
            char c;
            int u,v;
            cin >> c >> u >> v;
            if (u>v)
                swap(u,v);
            pii x(u,v);
            auto it = la.find(x);
            if (c == 'N') {
                if (it == la.end() || it->F != x)
                    la.insert({x,{i,1}});
                else
                    it->S.S++;
            } else {
                if (!--it->S.S) {
                    jizz(0,0,q,it->S.F,i,x);
                    la.erase(it);
                }
            }
        }
        for (const auto & x : la)
            jizz(0,0,q,x.S.F,q,x.F);
        gao(0,0,q);
    }
}

	#include <bits/stdc++.h>
	using namespace std;
	template<typename T> void mysort(T a, T b) {/miracle!/}
	int main()
	{
	int n;
	assert(cin >> n);
	assert(n >= 0);
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	assert(cin >> a[i]);
	mysort(a.begin(), a.end());
	assert(is_sorted(a.begin(), a.end()));
	}

	#include <bits/stdc++.h>
	using namespace std;
	int main()
	{
	int n;
	cin >> n;
	int *a = new int[n];
	for (int i = 0; i < n; ++i)
	cin >> a[i];
	cout << a[0] * a[0] << endl;
	cout << a[87] << endl;
	}

	int l = 1, r = n;
	while (l <= r) {
	int m = l + (r - l) / 2;
	if (ok(m))
	l = m + 1;
	else
	r = m - 1;
	}

	int p = 0;
	for (int s = 1 << __lg(n); s; s >>= 1)
	if (p + s <= n && ok(p + s))
	p += s;

	long long v[N + 1], s[N +１];
	for (int i = 1; i <= n; ++i)
	s[i] = s[i - 1] + v[i];
	while (Q--) {
	int l, r;
	cin >> l >> r;
	cout << s[r] - s[l - 1] << '\n';
	}

	for (int i = 1; i < n; ++i)
	for (int j = i; j > 0 && a[j] < a[j - 1]; --j)
	swap(a[j], a[j - 1]);

	#include<bits/stdc++.h>
	using namespace std;
	const int MAXN = 100005;
	const int SIZE = sqrt(MAXN);
	int a[MAXN], b[MAXN / SIZE + 1];
	void add(int i, int d)
	{
	a[i] += d;
	b[i / SIZE] += d;
	}
	int query(int i)
	{
	int ret = 0, k = i / SIZE;
	for (int j = 0; j < k; ++j)
	ret += b[j];
	for (int j = k * SIZE; j <= i; ++j)
	ret += a[j];
	return ret;
	}
	int query(int l, int r)
	{
	return query(r) - query(l - 1);
	}
	int main()
	{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	while (q--) {
	int c, x, y;
	cin >> c >> x >> y;
	if (c == 0)
	add(x, y);
	else
	cout << query(x, y) << '\n';
	}
	}

	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	const int N = 1e5 + 87;
	struct seg
	{
	int su, lc, rc;
	} S[20 * N];
	int ver[N], ptr;
	void init() {ptr = 1;}
	int newseg()
	{
	memset(S + ptr, 0, sizeof(seg));
	return ptr++;
	}
	int newseg(seg t)
	{
	S[ptr] = t;
	return ptr++;
	}
	void pull(int t) {S[t].su = S[S[t].lc].su + S[S[t].rc].su;}
	int n, q, a[N], b[N], C;
	int add(int t, int i, int v, int l = 0, int r = C)
	{
	t = t ? newseg(S[t]) : newseg();
	if (r - l == 1) {
	S[t].su += v;
	return t;
	}
	int m = (l + r) / 2;
	if (i < m)
	S[t].lc = add(S[t].lc, i, v, l, m);
	else
	S[t].rc = add(S[t].rc, i, v, m, r);
	pull(t);
	return t;
	}
	int qry(int lt, int rt, int k, int l = 0, int r = C)
	{
	if (r - l == 1)
	return l;
	int m = (l + r) / 2;
	int ls = S[S[rt].lc].su - S[S[lt].lc].su;
	if (ls >= k)
	return qry(S[lt].lc, S[rt].lc, k, l, m);
	else
	return qry(S[lt].rc, S[rt].rc, k - ls, m, r);
	}
	int main()
	{
	init();
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; ++i)
	scanf("%d", &a[i]);
	copy(a + 1, a + 1 + n, b);
	sort(b, b + n);
	C = unique(b, b + n) - b;
	for (int i = 1; i <= n; ++i) {
	a[i] = lower_bound(b, b + C, a[i]) - b;
	ver[i] = add(ver[i - 1], a[i], 1);
	}
	while (q--) {
	int l, r, k;
	scanf("%d%d%d", &l, &r, &k);
	printf("%d\n", b[qry(ver[l - 1], ver[r], k)]);
	}
	}

	#include <bits/stdc++.h>
	using namespace std;
	// nichijou
	#define REP(i,a,b) for (int i = (a), __e = (b); i < __e; ++i)
	#define RP(i,n) REP(i,0,n)
	#define PER(i,s,e) for (int i = (s) - 1, __e = (e); i >= __e; --i)
	#define PR(i,n) PER(i,n,0)
	#define REP1(i,a,b) for (int i = (a), __e = (b); i <= __e; ++i)
	#define RP1(i,n) REP1(i,1,n)
	#define PER1(i,s,e) for (int i = (s), __e = (e); i >= __e; --i)
	#define PR1(i,n) PER1(i,n,1)
	#define DO(n) REP(__i,0,n)
	template<typename T>
	void cmax(T & a, T b) {a = max(a, b);}
	template<typename T>
	void cmin(T & a, T b) {a = min(a, b);}

	// data type
	typedef long long ll;
	typedef pair<int,int> pii;
	typedef pair<ll,ll> pll;
	#define F first
	#define S second

	// STL container
	typedef vector<int> vi;
	typedef vector<ll> vll;
	#define SZ(a) ((int)a.size())
	#define ALL(a) a.begin(), a.end()
	#define CLR(a) a.clear()
	#define BK(a) (a.back())
	#define FT(a) (a.front())
	#define DB(a) a.pop_back()
	#define DF(a) a.pop_front()
	#define PB push_back
	#define EB emplace_back

	/* Reading input is now 20% cooler! */
	bool RD(void) {return true;}
	template<typename T>
	bool RD(T & a)
	{
	int c;
	while (!isdigit(c = getchar()));
	a = c&15;
	while (isdigit(c = getchar()))
	a = 10 * a + (c & 15);
	return 1;
	}
	bool RD(double & a) {return scanf("%lf", &a) == 1;}
	bool RD(char & a) {return scanf(" %c", &a) == 1;}
	bool RD(char * a) {return scanf("%s", a) == 1;}
	template<typename T, typename ... TT>
	bool RD(T & a, TT & ... b) {return RD(a) && RD(b...);}

	/* Do princesses dream of magic sheep? */
	#define RI(a) int a; RD(a)
	#define RII(a,b) RI(a); RI(b)
	#define RIII(a,b,c) RI(a); RII(b,c)
	#define RIIII(a,b,c,d) RI(a); RIII(b,c,d)

	/* For it's time for you to fulfill your output. */
	void PT(const char * a) {fputs(a, stdout);}
	void PT(char * a) {fputs(a, stdout);}
	template<typename T>
	void PT(const T a)
	{
	static const int maxd = 25;
	static char d[maxd];
	int i = maxd - 1;
	T t = a;
	do {
	d[--i] = (t % 10) \| 48;
	} while (t /= 10);
	PT(d + i);
	}
	void PT(const double a) {printf("%.16f", a);}
	void PT(const char a) {putchar(a);}

	/* The line will last forever! */
	void PL(void) {PT('\n');}
	template<typename T, typename ... TT>
	void PL(const T a, const TT ... b) {PT(a); if (sizeof...(b)) PT(' '); PL(b...);}

	/* Good Luck && Have Fun ! */
	const int N = 1e5 + 87;
	const int D = __lg(N)+1;
	struct node
	{
	int s;
	nodel,r;
	} mem[ND2];
	node * rt[N],* ptr=mem;
	node * add(node * t,int l,int r,int i)
	{
	t=t?new(ptr++) node(*t):new(ptr++) node();
	++t->s;
	if (r-l==1)
	return t;
	int m=l+((r-l)>>1);
	if (i<m)
	t->l=add(t->l,l,m,i);
	else
	t->r=add(t->r,m,r,i);
	return t;
	}
	int qry(node*t,int l,int r,int i,int s=0)
	{
	if (!t)
	return s;
	if (r==i+1)
	return s+t->s;
	int m=l+((r-l)>>1);
	if (i<m)
	return qry(t->l,l,m,i,s);
	return qry(t->r,m,r,i,(t->l?t->l->s:0) + s);
	}
	int main()
	{
	RII(n,m);
	RP1(i,n) {
	RI(b);
	rt[i] = add(rt[i-1],1,n+1,b);
	}
	DO(m) {
	RII(p,k);
	++p;
	int lo = 1, hi = n;
	while (lo <= hi) {
	int mi=(lo+hi)>>1;
	if (qry(rt[min(p+mi,n)],1,n+1,mi) - qry(rt[max(p-mi-1,0)],1,n+1,mi) >= k)
	hi = mi - 1;
	else
	lo = mi + 1;
	}
	PL(lo);
	}
	}

2021 一中資奧研習