12844 XOR https://www.acmicpc.net/problem/12844
1395 스위치 https://www.acmicpc.net/problem/1395
1. 자동차 공장
상근이가 최고참 상사인 계급도가 트리 형태로 구성된 회사가 존재한다.
1. p a x가 주어진 경우 A의 모든 부하의 월급을 X만큼 증가시킨다. (-10,000 ≤ X ≤ 10,000)
2. u a가 주어진 경우에는 A의 월급을 출력한다.
위와 같은 두 쿼리를 처리해야 한다.
트리 형태의 계급도를 dfs를 돌려서 번호를 매기면 1차원으로 만들 수 있으므로 segment tree에 저장시킬 수 있다.
A의 시작하는 번호와 끝나는 번호를 lazy propagation으로 update시키면 쿼리를 해결할 수 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
struct Segment {
int size;
vector<ll> tree, lazy;
Segment(int s) {
size = s;
tree.resize(4 * s, 0);
lazy.resize(4 * s, 0);
}
void propagate(int node, int nL, int nR) {
if (lazy[node]) {
if (nL != nR) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
tree[node] += lazy[node] * (nR - nL + 1);
lazy[node] = 0;
}
}
void update(int node, int val, int l, int r, int nL, int nR) {
propagate(node, nL, nR);
if (r < nL || l > nR) return;
if (l <= nL && nR <= r) {
lazy[node] += val;
propagate(node, nL, nR);
return;
}
int mid = (nL + nR) / 2;
update(node * 2, val, l, r, nL, mid);
update(node * 2 + 1, val, l, r, mid + 1, nR);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int l, int r, int val) {
update(1, val, l, r, 0, size - 1);
}
ll query(int node, int l, int r, int nL, int nR) {
propagate(node, nL, nR);
if (r < nL || l > nR) return 0;
if (l <= nL&& nR <= r) return tree[node];
int mid = (nL + nR) / 2;
return query(node * 2, l, r, nL, mid) + query(node * 2 + 1, l, r, mid + 1, nR);
}
ll query(int l,int r) {
return query(1, l, r, 0, size - 1);
}
};
int N, M;
vector<int> adj[500001];
int cost[500001];
int s[500001], e[500001];
int order = -1;
void dfs(int here) {
s[here] = ++order;
for (int next : adj[here]) {
if (s[next] == -1)
dfs(next);
}
e[here] = order;
}
int main() {
memset(s, -1, sizeof s);
scanf("%d%d", &N, &M);
Segment seg(N);
scanf("%d", &cost[0]);
for (int n = 1, u;n < N;n++) {
scanf("%d%d", &cost[n], &u);
adj[u - 1].push_back(n);
}
dfs(0);
for (int n = 0;n < N;n++)
seg.update(s[n], s[n], cost[n]);
for (int m = 0;m < M;m++) {
char c;
int a, x;
scanf(" %c", &c);
if (c == 'p') {
scanf("%d%d", &a, &x);
--a;
if (s[a] == e[a]) continue;
seg.update(s[a] + 1, e[a], x);
}
else {
scanf("%d", &a);
--a;
printf("%lld\n", seg.query(s[a], s[a]));
}
}
return 0;
}
| cs |
2. XOR
- 특정 구간 a,b 에 c를 xor 한다.
- 특정 구간 a,b 를 xor 한 값을 출력한다.
위와 같은 두 쿼리를 처리해야 한다.
update하는 구간이 짝수 개면 xor을 할 필요가 없는점을 조심하자.
#include <cstdio>
#include <vector>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
struct Segment {
int size;
vector<int> tree;
vector<int> lazy;
Segment(int s) {
size = s;
tree.resize(4 * s, 0);
lazy.resize(4 * s, 0);
}
int init(int node, int nL, int nR, int arr[500001]) {
if (nL == nR) return tree[node] = arr[nL];
int mid = (nL + nR) / 2;
return tree[node] = init(node * 2, nL, mid, arr) ^ init(node * 2 + 1, mid + 1, nR, arr);
}
int init(int arr[500001]) {
return init(1, 0, size - 1, arr);
}
void propagate(int node, int nL, int nR) {
if (lazy[node]) {
if (nL != nR) {
lazy[node * 2] ^= lazy[node];
lazy[node * 2 + 1] ^= lazy[node];
}
if ((nL - nR + 1) & 1) tree[node] ^= lazy[node];
lazy[node] = 0;
}
}
void update(int node, int val, int l, int r, int nL, int nR) {
propagate(node, nL, nR);
if (l > nR || r < nL) return;
if (l <= nL && nR <= r) {
lazy[node] = lazy[node] ^ val;
propagate(node, nL, nR);
return;
}
int mid = (nL + nR) / 2;
update(node * 2, val, l, r, nL, mid);
update(node * 2 + 1, val, l, r, mid + 1, nR);
tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
}
void update(int val, int l, int r) {
update(1, val, l, r, 0, size - 1);
}
int query(int node, int l, int r, int nL, int nR) {
propagate(node, nL, nR);
if (l > nR || r < nL) return 0;
if (l <= nL && nR <= r) return tree[node];
int mid = (nL + nR) / 2;
return query(node * 2, l, r, nL, mid) ^ query(node * 2 + 1, l, r, mid + 1, nR);
}
int query(int l, int r) {
return query(1, l, r, 0, size - 1);
}
};
int N, M;
int arr[500001];
int main() {
scanf("%d", &N);
Segment seg(N);
for (int n = 0;n < N;n++) {
int u;
scanf("%d", &arr[n]);
}
seg.init(arr);
scanf("%d", &M);
for (int m = 0;m < M;m++) {
int t, u, v, d;
scanf("%d", &t);
if (t == 1) {
scanf("%d%d%d", &u, &v, &d);
seg.update(d, min(u, v), max(u, v));
}
else {
scanf("%d%d", &u, &v);
printf("%d\n", seg.query(min(u, v), max(u, v)));
}
}
return 0;
}
| cs |
3. 스위치
- 특정 구간 a,b 에 스위치 상태를 반전시킨다.
- 특정 구간 a,b 에 켜져있는 스위치의 갯수를 출력한다.
위와 같은 두 쿼리를 처리해야 한다.
update시킬때 lazy값을 bool값으로 주고 layer가 한단계씩 올라갈수록 반전시켜 주어야한다.
#include <cstdio>
#include <vector>
using namespace std;
struct Segment {
int size;
vector<int> tree;
vector<bool> lazy;
Segment(int s) {
size = s;
tree.resize(4 * s, 0);
lazy.resize(4 * s, false);
}
void propagate(int node, int nL, int nR) {
if (lazy[node]) { //반전 시켜라
if (nL != nR) {
lazy[node * 2] = !lazy[node * 2];
lazy[node * 2 + 1] = !lazy[node * 2 + 1];
}
tree[node] = (nR - nL + 1) - tree[node];
lazy[node] = 0;
}
}
void update(int node, int l, int r, int nL, int nR) {
propagate(node, nL, nR);
if (l > nR || r < nL) return;
if (l <= nL && nR <= r) {
lazy[node] = !lazy[node];
propagate(node, nL, nR);
return;
}
int mid = (nL + nR) / 2;
update(node * 2, l, r, nL, mid);
update(node * 2 + 1, l, r, mid + 1, nR);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void update(int l, int r) {
update(1, l, r, 0, size - 1);
}
int query(int node, int l, int r, int nL, int nR) {
propagate(node, nL, nR);
if (l > nR || r < nL) return 0;
if (l <= nL && nR <= r) return tree[node];
int mid = (nL + nR) / 2;
return query(node * 2, l, r, nL, mid) + query(node * 2 + 1, l, r, mid + 1, nR);
}
int query(int l, int r) {
return query(1, l, r, 0, size - 1);
}
};
int N, M;
int main() {
scanf("%d%d", &N, &M);
Segment seg(N);
for (int m = 0;m < M;m++) {
int q, u, v;
scanf("%d%d%d", &q, &u, &v);
--u, --v;
if (q) printf("%d\n", seg.query(u, v));
else seg.update(u, v);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기