개요
꽤 오래 전에 했던 버추얼있데, 시간이 좀 지나서 어떤 문제였는지 까먹었다.
E번을 구현하고 리뷰하려고 했지만, E 구현에 g++이 필요해 그 환경설정을 한다고 미뤄뒀다가 지금에서야 리뷰를 하게 됐다.
D번까지는 전반적으로 쉬웠고, E번에서 문제도 잘 단순화 했고, 적절한 자료구조를 사용했지만 비효율적인 구현으로 인해 TLE가 났다는 것이 아쉬웠다.
이 TLE가 발생하지 않고 조금 더 효율적으로 구현하려면 종만북에서 소개되는 Treap이라는 자료구조가 필요한데, 직접 구현하기에는 까다롭고 g++에서 지원하는 order statistics tree를 사용하면 편하게 구현할 수 있다.
에디토리얼에서는 이것 없이 Fenwick Tree와 lower_bound를 적절히 사용해서 구현했는데, 이것도 리뷰 할 것이다.
C번
C번 문제: 그리디 구현
$n$은 항상 짝수이며, $\frac{n}{2}$개의 음이 아닌 정수로 이루어진 $b_i$가 주어진다.
이 때, $b_i = a_i + a_{n-i+1}$을 만족시키고, 단조증가($a_i \leq a_{i+1}$)하며, 음이 아닌 정수로 이루어진 수열 $a_i$를 구해야 한다.
풀이 보기
$b_1$부터 차례로 만들어가면 되는데, 조건을 만족하는 한도에서 $a_i$는 현재 만들 수 있는 것 중에서 가장 작게, $a_{n-i+1}$은 가장 크게 만들어나가면 된다.
(이 때 둘 사이의 갭이 크면 클 수록 좋다.)
즉, $a_i \geq a_{i-1}$이며 $a_{n-i+1} \leq a_{n-i+2}$를 만족하는 경우 중 갭이 가장 큰 경우를 골라나가면 된다.
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 2e5+10;
i64 n, ar[MAXN], br[MAXN];
void input() {
cin >> n;
FOR(i, 0, n/2) cin >> br[i];
}
int solve() {
i64 cur = 0;
ar[0] = 0ll, ar[n-1] = br[0];
FOR(i, 1, n/2) {
ar[n-i-1] = min(br[i]-ar[i-1], ar[n-i]);
ar[i] = br[i]-ar[n-i-1];
}
FOR(i, 0, n) cout << ar[i] << ' '; cout << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
D번
D번 문제: 그래프 그리디
$n$개의 정점과 $m$개의 간선으로 이루어진 무향 무가중 그래프가 주어진다.
이 그래프에서 각 정점마다 $1$, $2$, $3$ 중 하나의 가중치를 부여하여, 모든 간선에 대해 간선의 양 끝 점의 합이 홀수가 되도록 하는 방법의 수를 구해야 한다.
풀이 보기
일단 간선의 양 끝 정점의 합이 홀수가 되게 한다는 것은, 정점들을 짝수, 홀수인 그룹으로 나눴을 때 두 정점은 서로 다른 그룹에 속해야 한다는 것이다.
주어진 그래프가 연결 그래프라는 소리는 없었으나, 일단 하나의 연결 그래프에 대해서만 고려해보자.
(여러개의 컴포넌트가 있을 경우는 그냥 각 컴포넌트의 경우의 수를 모두 곱하면 된다.)
임의의 한 시작 정점 $u$에 아무 가중치나 부여해보면 $u$와 연결된 정점 $v$들은 모두 $u$와 다른 가중치를 가져야 할 것이며, 이것은 BFS처럼 퍼져나가게 된다는 것을 알 수 있다.
만약 가중치를 부여해야 할 정점이 이미 가중치를 가지고 있고, 그것이 현재 정점과 같은 가중치이면 어떻게 하든 정점을 칠할 방법이 없는 것이다.
이와 같은 방법의 모든 정점에 색을 다 입힌 후에 시작 정점을 홀수로 칠하는 경우, 짝수로 칠하는 경우 각각에 대해서 경우의 수를 구해주면 된다.
(이 때, 홀수의 경우 $1$, $3$ 두 가지 경우로 칠할 수 있다는 것을 염두에 두어야 한다.)
소스코드 보기
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 998244353;
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = (a*a) % MOD, n /= 2) { if(n%2) ret *= a, ret %= MOD; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
int n, m;
vi ar;
vvi g;
set<int> rem;
void input() {
cin >> n >> m;
g = vvi(n, vi());
ar = vi(n, -1);
while(m--) {
int u, v; cin >> u >> v; --u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
}
int solve() {
i64 ans = 1;
rem.clear();
FOR(i, 0, n) rem.insert(i);
while(rem.size()) {
vi cur;
queue<int> q;
q.push(*rem.begin());
ar[*rem.begin()] = 0;
while(q.size()) {
int u = q.front(); q.pop();
cur.pb(u);
rem.erase(u);
for(int v : g[u]) {
if(ar[v] == -1) ar[v] = ar[u]^1, q.push(v);
else if(ar[v] == ar[u]) {
cout << 0 << ENDL;
return 0;
}
}
}
int cnt = 0;
for(int u : cur) {
if(ar[u]) ++cnt;
}
ans *= ((POW(2, cnt) + POW(2, cur.size()-cnt)) % MOD);
ans %= MOD;
}
cout << ans << ENDL;
return 0;
}
// ................. main .................. //
void execute() {
int TT; cin >> TT;
while(TT--)
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
E번
E번 문제: 쿼리 SegTree Fenwick Order Statistics Tree
$n$개의 원소를 가진 두 수열 $a$, $b$가 있고, 각각은 $[1..n]$이 딱 $1$번씩만 등장한다.
이후 $q$개의 두 종류의 쿼리가 들어온다.
$1$ $s_a$ $e_a$ $s_b$ $e_b$ : $a[s_a..e_a]$와 $b[s_b..e_b]$에 공통으로 존재하는 원소의 수를 찾아라
$2$ $p$ $q$ : 수열 $b$에서 $p$, $q$의 위치를 바꿔라.
풀이 보기
한 쿼리를 $O(\log{n})$혹은 $O(\log^2{n})$만에 처리해야 한다.
$2$번 쿼리는 그냥 자리만 바꾸면 된다고 치고, $1$번 쿼리를 어떻게 처리해야 할까?
일단 기본적인 데이터를 가공하지 않고 $1$번을 처리하는 방법은 나로써는 $O(n)$ 밖에 생각이 나지 않는다.
이렇게 막막할 때마다 쓰기 좋았던 방법이 있는데, 바로 배열의 idx와 val의 위치를 바꾸는 것이다.
즉, $a[idx] = val$로 배열을 표현했다면, $a’[val] = idx$로 표현을 하는 것이다.
이런 방법은 Segment Tree문제들을 풀 때 종종 유용하게 사용된다.
이로써 얻을 수 있는 이득은 서로 중복 여부를 확인하는데만 쓰였던 val을 index로 보내버렸다는 것에 있다.
사실 우리는 idx 구간에 존재하는 원소의 val을 알고 싶은게 아니다. val은 단지 중복 여부 판단에 쓰일 뿐이다.
여기서 중복 판단이란 두 idx가 같은 val을 가지고 있느냐는 것인데, 변형된 버전에서는 두 idx가 같은 index인가를 알아보는 것이다.
즉, $a[x] = b[y]$인지를 알고 싶다면, 변형된 배열$a’$, $b’$에서 각각 $x$, $y$가 등장하는 위치가 같은지를 알아보면 된다.
언뜻 보기에는 왜 이렇게 비효율적인 방법을 사용하는지 의문이 들 수 있지만, 이 방법은 두 배열의 “공유하는 index”를 이용한다는 장점이 있다.
두 배열이 공유하는 index를 가질 때만 같은 값을 가지는데, 이것을 아예 합쳐버리면 어떻게 될까?
즉, $ab[val] = (idx_a, idx_b)$ 형태로 만들어버리는 것이다.
이렇게 하면 값이 마치 2차원 평면에서의 좌표처럼 변하고, $1$번 쿼리를 다음과 같이 단순화 할 수 있다.
2차원 평면에 좌표들이 있을 때, 특정 $[(s_x, s_y), (e_x, e_y)]$구간에 속하는 점의 수를 구해라.
이 문제는 꽤나 전형적인 문제이고, 특히나 점의 수가 $2 \cdot 10^5$밖에 안 되는 상황에서는 효율적으로 쿼리를 처리할 수 있는 방법들이 있다.
첫 번째로는 쿼드트리를 사용하는 방법인데, 평면을 재귀적으로 4등분하여 탐색하는 방법이다.
점을 추가할 때는 $O(\log{n})$번의 재귀만을 거치면 되고, 구간 쿼리를 할 때 역시 $O(\log{n})$번의 재귀만을 거치면 된다.
단, 구간 쿼리 시 $O(\log{n})$에 붙는 상수 값이 크고, 점을 추가 할 때 현재 점을 가지고 있는 구간들을 map[구간]에 저장해두고 구간 쿼리 시 해당 구간이 map에 존재하지 않는다면 탐색을 하지 않는 식으로 구현했는데, map 자체의 시간복잡도도 커서 TLE가 발생하였다.
두 번째 방법은 2D segtree를 sparse하게 구현하는 것이다.
sparse하지 않는 2D segtree의 경우 $x$축을 구간으로 나누고, 각 $x$축 구간마다 $y$를 저장하는 segtree를 만드는 방식으로 구현된다.
하지만 이렇게 구현을 하면 공간 복잡도가 $O(n^2)$이 돼 버리기 때문에 다른 방법을 생각해야 한다.
점의 수 자체가 적기 때문에, 각 $x$구간마다 $y$를 segtree로 저장하는 대신에 set형태로 저장하면 공간을 효율적으로 사용 할 수 있다.
점을 추가하는 쿼리는 그냥 $x$구간마다 set에 insert를 하면 되지만, 구간 쿼리에서는 set에서 $y$보다 작은 원소의 수를 빠르게 구해야한다.
하지만 이 연산은 STL set에 구현되어 있지 않고, g++에 내장된 order statistics tree를 사용하면 쉽게 구현할 수 있다.
세 번째 방법은 두 번째 방법에서 order statistics tree를 사용하지 않고 구현한 방법이다.
set을 두 개의 배열로 대신해서 구현을 한다.
$vals$는 해당 $x$구간에 존재할 수 있는 $y$들을 저장하고, $f$는 그 $y$가 총 몇 개나 등장했는지를 저장한다.
이 때의 문제점이 $1$번 쿼리로 인해 해당 구간에 존재하는 $y$값이 바뀔 수 있다는 것인데, 이것은 모든 쿼리에 대해 전처리를 해서 해당 구간에 존재할 수 있는 모든 $y$를 저장해두면 해결된다.
쿼리의 수도 $O(2 \cdot 10^5$이기 때문에 시간복잡도에 대한 영향도 없다.
QuadTree를 사용한 코드 보기(TLE)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
class FastIO {
int fd, bufsz;
char *buf, *cur, *end;
public:
FastIO(int _fd = 0, int _bufsz = 1 << 20) : fd(_fd), bufsz(_bufsz) {
buf = cur = end = new char[bufsz];
}
~FastIO() {
delete[] buf;
}
bool readbuf() {
cur = buf;
end = buf + bufsz;
while(true) {
size_t res = fread(cur, sizeof(char), end - cur, stdin);
if(res == 0) break;
cur += res;
}
end = cur;
cur = buf;
return buf != end;
}
int r() {
while(true) {
if(cur == end) readbuf();
if(isdigit(*cur) || *cur == '-') break;
++cur;
}
bool sign = true;
if(*cur == '-') {
sign = false;
++cur;
}
int ret = 0;
while(true) {
if(cur == end && !readbuf()) break;
if(!isdigit(*cur)) break;
ret = ret * 10 + (*cur - '0');
++cur;
}
return sign ? ret : -ret;
}
} sc;
const int MAXN = 1<<18;
int n, qq, xr[MAXN], yr[MAXN], yidx[MAXN];
map<pair<ii, ii>, int> mp;
void input() {
n = sc.r(), qq = sc.r();
int p;
FOR(i, 0, n) p = sc.r(), xr[p-1] = i;
FOR(i, 0, n) p = sc.r(), yr[p-1] = i, yidx[i] = p-1;
//FOR(i, 0, n) cout << xr[i] << ' '; cout << ENDL;
//FOR(i, 0, n) cout << yr[i] << ' ';
}
void add(int y, int x, int t, ii s = { 0, 0 }, ii e = { MAXN-1, MAXN-1 }) {
if(y < s.first || e.first < y || x < s.second || e.second < x) return;
int my = (s.first + e.first) / 2, mx = (s.second + e.second) / 2;
if((mp[{ s, e }] += t) == 0) mp.erase({ s, e });
if(s != e) {
add(y, x, t, { s.first, s.second }, { my, mx });
add(y, x, t, { my+1, s.second }, { e.first, mx });
add(y, x, t, { s.first, mx+1 }, { my, e.second });
add(y, x, t, { my+1, mx+1 }, { e.first, e.second });
}
}
int sum(ii s, ii e, ii ns = { 0, 0 }, ii ne = { MAXN-1, MAXN-1 }) {
if(mp.find({ ns, ne }) == mp.end()) return 0;
if(s.first <= ns.first && ne.first <= e.first && s.second <= ns.second && ne.second <= e.second) return mp[{ ns, ne }];
if(ne.first < s.first || e.first < ns.first || ne.second < s.second || e.second < ns.second) return 0;
int my = (ns.first + ne.first) / 2, mx = (ns.second + ne.second) / 2;
return sum(s, e, ns, { my, mx })
+ sum(s, e, { ns.first, mx+1 }, { my, ne.second })
+ sum(s, e, { my+1, ns.second }, { ne.first, mx })
+ sum(s, e, { my+1, mx+1 }, { ne.first, ne.second });
}
int solve() {
FOR(i, 0, n) add(xr[i], yr[i], 1);
while(qq--) {
int tt; tt = sc.r();
if(tt == 1) {
int sy, sx, ey, ex; sy = sc.r(), ey = sc.r(), sx = sc.r(), ex = sc.r(); --sy, --sx, --ey, --ex;
//debug(sy, sx, ey, ex);
cout << sum({ sy, sx }, { ey, ex }) << ENDL;
} else {
int a, b; a = sc.r(), b = sc.r();
a = yidx[a-1], b = yidx[b-1];
add(xr[a], yr[b], 1), add(xr[b], yr[a], 1);
add(xr[a], yr[a], -1), add(xr[b], yr[b], -1);
swap(yr[a], yr[b]);
swap(yidx[yr[a]], yidx[yr[b]]);
assert(mp.size() < 4e6);
//debug(yr[a], yr[b], yidx[yr[a]], yidx[yr[b]]);
//FOR(i, 0, n) cout << xr[i] << ' '; cout << ENDL;
//FOR(i, 0, n) cout << yr[i] << ' '; cout << ENDL;
}
}
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
int main(void) {
#ifdef LOCAL_BOOKNU
freopen("input.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
// ......................................... //
sparse 2D segtree를 사용한 코드 보기(set)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treeset; // key, val, comp, implements, 노드 불변 규칙
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 떄 이상하게 작동할 수 있음
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
inline i64 POW(i64 a, i64 n) {
assert(0 <= n);
i64 ret;
for(ret = 1; n; a = a*a, n /= 2) { if(n%2) ret *= a; }
return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
os << "[";
int cnt = 0;
for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //
const int MAXN = 2e5+10;
struct fenwick {
int n;
vector<treeset> t;
fenwick(int _n) : n(_n), t(n+1, treeset()) { }
void add(int x, int y) {
for(++x; x < t.size(); x += (x&-x)) {
t[x].insert(y);
}
}
void remove(int x, int y) {
for(++x; x < t.size(); x += (x&-x)) {
t[x].erase(y);
}
}
int sum(int x, int y) {
// if(x < 0 || y < 0) return 0;
int ret = 0;
for(++x, ++y; x > 0; x -= (x&-x)) {
ret += t[x].order_of_key(y);
}
return ret;
}
int sum(int sx, int ex, int sy, int ey) {
return sum(ex, ey) - sum(sx-1, ey) - sum(ex, sy-1) + sum(sx-1, sy-1);
}
} ft(MAXN);
int n, qq, xr[MAXN], yr[MAXN], yidx[MAXN];
void input() {
cin >> n >> qq;
int p;
FOR(i, 0, n) cin >> p, xr[p-1] = i;
FOR(i, 0, n) cin >> p, yr[p-1] = i, yidx[i] = p-1;
}
int solve() {
FOR(i, 0, n) ft.add(xr[i], yr[i]);
while(qq--) {
int tt; cin >> tt;
if(tt == 1) {
int sy, sx, ey, ex; cin >> sx >> ex >> sy >> ey; --sy, --ey, --sx, --ex;
cout << ft.sum(sx, ex, sy, ey) << ENDL;
} else {
int a, b; cin >> a >> b;
a = yidx[a-1], b = yidx[b-1];
ft.remove(xr[a], yr[a]), ft.remove(xr[b], yr[b]);
ft.add(xr[a], yr[b]), ft.add(xr[b], yr[a]);
swap(yr[a], yr[b]);
swap(yidx[yr[a]], yidx[yr[b]]);
}
}
return 0;
}
// ................. main .................. //
void execute() {
input(), solve();
}
#ifndef LOCAL_BOOKNU
int main(void) {
cin.tie(0), ios_base::sync_with_stdio(false);
execute();
return 0;
}
#endif
// ......................................... //
sparse 2D segtree를 사용한 코드 보기(배열)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
int n, m;
int a[N], b[N], pos[N];
vector<int> f[N];
vector<int> vals[N];
void addupd(int x, int y){
for (int i = x; i < N; i |= i + 1)
vals[i].push_back(y);
}
void addget(int x, int y){
if (x < 0 || y < 0) return;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
vals[i].push_back(y);
}
void upd(int x, int y, int val){
for (int i = x; i < N; i |= i + 1)
for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j < int(f[i].size()); j |= j + 1)
f[i][j] += val;
}
int get(int x, int y){
if (x < 0 || y < 0) return 0;
int res = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
for (int j = lower_bound(vals[i].begin(), vals[i].end(), y) - vals[i].begin(); j >= 0; j = (j & (j + 1)) - 1)
res += f[i][j];
return res;
}
struct query{
int t, la, ra, lb, rb;
query(){};
};
query q[N];
int main() {
scanf("%d%d", &n, &m);
forn(i, n){
scanf("%d", &a[i]);
--a[i];
pos[a[i]] = i;
}
forn(i, n){
scanf("%d", &b[i]);
--b[i];
b[i] = pos[b[i]];
}
forn(i, m){
scanf("%d", &q[i].t);
if (q[i].t == 1){
scanf("%d%d%d%d", &q[i].la, &q[i].ra, &q[i].lb, &q[i].rb);
--q[i].la, --q[i].ra, --q[i].lb, --q[i].rb;
}
else{
scanf("%d%d", &q[i].lb, &q[i].rb);
--q[i].lb, --q[i].rb;
}
}
vector<int> tmp(b, b + n);
forn(i, n) addupd(i, b[i]);
forn(i, m){
if (q[i].t == 1){
addget(q[i].rb, q[i].ra);
addget(q[i].lb - 1, q[i].ra);
addget(q[i].rb, q[i].la - 1);
addget(q[i].lb - 1, q[i].la - 1);
}
else{
addupd(q[i].lb, b[q[i].lb]);
addupd(q[i].rb, b[q[i].rb]);
swap(b[q[i].lb], b[q[i].rb]);
addupd(q[i].lb, b[q[i].lb]);
addupd(q[i].rb, b[q[i].rb]);
}
}
forn(i, n) b[i] = tmp[i];
forn(i, N){
sort(vals[i].begin(), vals[i].end());
vals[i].resize(unique(vals[i].begin(), vals[i].end()) - vals[i].begin());
f[i].resize(vals[i].size(), 0);
}
forn(i, n)
upd(i, b[i], 1);
forn(i, m){
if (q[i].t == 1){
int res = 0;
res += get(q[i].rb, q[i].ra);
res -= get(q[i].lb - 1, q[i].ra);
res -= get(q[i].rb, q[i].la - 1);
res += get(q[i].lb - 1, q[i].la - 1);
printf("%d\n", res);
}
else{
upd(q[i].lb, b[q[i].lb], -1);
upd(q[i].rb, b[q[i].rb], -1);
swap(b[q[i].lb], b[q[i].rb]);
upd(q[i].lb, b[q[i].lb], 1);
upd(q[i].rb, b[q[i].rb], 1);
}
}
return 0;
}
후기
E번에서 “2D SegTree는 segtree안에 segtree를 넣어야 돼서 공간복잡도가 $O(n^2)$이다.” 라는 고정관념 때문에 그 안에 set을 넣는다는 생각을 하지 못했다.
문제 압축까지 다 하고 QuadTree로 열심히 구현했으나 TLE가 난게 아쉽다.