(Lazy Propagation) 2820 자동차 공장

2820 자동차 공장 https://www.acmicpc.net/problem/2820
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; } Colored by Color Scripter

cs

2. XOR

1. 특정 구간 a,b 에 c를 xor 한다.
2. 특정 구간 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; } Colored by Color Scripter

cs

3. 스위치

1. 특정 구간 a,b 에 스위치 상태를 반전시킨다.
2. 특정 구간 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; } Colored by Color Scripter

cs

11097 도시계획

11097 도시 계획 https://www.acmicpc.net/problem/11097

리스트가 하나 주어진다.
이 리스트는 $i$에서 $j$로 갈 수 있는 경로가 존재한다면 1, 절대 못간다면 0으로 나타냈다.
우리는 가장 적은 간선을 사용해서 이 리스트처럼 갈 수 있도록 해야한다.
이때 필요한 가장 적은 간선의 갯수와 그 간선을 구하는 문제이다.

주어진 리스트로 일단 SCC를 구해서 SCC내부의 정점들이 $u, v, k, d$라면 
$u$->$v$, $v$->$k$, $k$->$d$, $d$->$u$가 최소 간선을 사용해서 만드는 방법은 쉽게 구할 수 있다.

문제는 서로 다른 SCC간에 최적 간선이다.
주어진 리스트에서 불필요한 간선이 있기 때문에 이 간선들을 삭제시켜야 하는데 
플로이드 와샬 알고리즘을 사용하면 해결할 수 있다.

코드가 너무길어 부분만 올린다.

for (int n = 0;n < N;n++) {             for (int m = 0;m < N;m++) {                 //그래프 압축 후 다른 scc간에 연결 시켜줌                 if (map[n][m] == '0' || n == m || scc[n] == scc[m]) continue;                 adj_scc[scc[n]][scc[m]] = true;               }         }         //연결된것은 최적값이 아님 (scc간에 연결은 간선 1개면 충분)         for (int k = 0;k < scc_cnt;k++) {             for (int n = 0;n < scc_cnt;n++) {                 for (int m = 0;m < scc_cnt;m++) {                     //n->k, k->m으로 간다면 n->m은 삭제 가능                     if (adj_scc[n][m] && adj_scc[n][k] && adj_scc[k][m]) adj_scc[n][m] = 0;                 }             }         }         vector<pair<int, int>> ans;                  // <답 1차 저장> scc내부간에 간선 저장         for (int n = 0;n < scc_cnt;n++) {             int getsize = (int)group_scc[n].size();             if (getsize > 1) {        // scc내부 정점이 여러개라면 u->v->d->k->u 형식으로 묶어줌 (최소)                 for (int m = 0;m < getsize - 1;m++)                     ans.push_back({ group_scc[n][m],group_scc[n][m + 1] });                 ans.push_back({ group_scc[n][getsize - 1],group_scc[n][0] });             }         }         // <답 2차 저장> 서로 다른 scc간에 간선 저장         for (int n = 0;n < scc_cnt;n++) {             for (int m = 0;m < scc_cnt;m++) {                 if (adj_scc[n][m]) {                     //순서에 상관없으므로 첫번째 걸로 저장                     ans.push_back({ group_scc[n][0], group_scc[m][0] });                 }             }         } Colored by Color Scripter

cs

                                                                       <600 돌파 !!!>