rofn123

#include int tree[400000] = {}; //segment treechar lazy[400000] = {}; //0이면 none, 1이면 스위치를 반전시켜야 한다는 의미int lazyUpdate (int s, int e, int node) { //lazy propagation if(lazy[node]) { //1이라면 이 범위의 스위치들의 상태를 반전시켜야 함 tree[node] = (e-s+1)-tree[node]; //범위의 개수에 기존의 스위치 중 켜져 있는 것을 빼면 반전된 스위치 중 켜져 있는 개수를 의미하게 됨 if(s!=e) { //말단 노드가 아니라면 lazy[node*2] ^= lazy[node]; //0이면 1이, 1이면 0이 됨 lazy[node*2+1] ^..

#include int arr[500000] = {};int tree[2000000] = {};int lazy[2000000] = {};int init(int s, int e, int node) { if(s==e) return tree[node] = arr[s]; int m=(s+e)/2; return tree[node] = init(s,m,node*2)^init(m+1,e,node*2+1);}void lazyUpdate(int s, int e, int node) { if(lazy[node]) { if(((e-s)&1)==0) tree[node] ^= lazy[node]; if(s!=e) { lazy[node*2] ^= lazy[node]; lazy[node*2+1] ^= lazy[node..

#include int arr[500000] = {};int tree[2000000] = {};int lazy[2000000] = {};int init(int s, int e, int node) { if(s==e) return tree[node] = arr[s]; int m=(s+e)/2; return tree[node] = init(s,m,node*2)^init(m+1,e,node*2+1);}void lazyUpdate(int s, int e, int node) { if(lazy[node]) { if(((e-s)&1)==0) tree[node] ^= lazy[node]; if(s!=e) { lazy[node*2] ^= lazy[node]; lazy[node*2+1] ^= lazy[node..

#include int tree[2][400004]={};int arr[100001]={};int update(int s, int e, int node, int index, int dif, int isMax) { //isMax는 최소인지 최대인지를 구별하기 위한 변수입니다. if(s>index || er)?r:l; //최소 else return tree[isMax][node] = (l>r)?l:r; //최대}int find(int s, int e, int node, int l, int r, int isMax) { if(s>r || eR)?R:L; //최소 else return (L>R)?L:R; //최대}int main(void) { int t,n,k; scanf("%d",&t); while(t--) {..

#include #include typedef struct A{int x,y; /*x (index) y (value)*/}A;int tree[2000000] = {};int compare(const void *a, const void *b) { //value 기준 오름차순 정렬 return (*(A*)a).y - (*(A*)b).y;}int update(int s, int e, int node, int index) { if(s>index || er || e=0; i--) { ans += find(0,n-1,1,0,arr[i].x-1); update(0,n-1,1,arr[i].x); } printf("%lld",ans);} 풀이 : 세그먼트 트리,정렬 0. 세그먼트 트리를 준비합니다. 특정 index..

https://www.acmicpc.net/problem/1168#include int tree[400004] = {};int update(int s, int e, int node, int i, int dif) { if(s>i || e=cnt) find(s,m,node*2,cnt); else find(m+1,e,node*2+1,cnt-tree[node*2]);}int main(void) { int n,k,a=0,c=0,d; scanf("%d %d",&n,&k); c=n; a=k; for(int i=1; ic) { a %= c; if(a==0) a = c; } } printf(">");} 풀이 : 세그먼트 트리, 몇번째로 작은 수 인가? 반복문으로 구현한다면, 요세푸스 문제의 경우 아직 선택되지..

#include #define M 1000000007long long tree[4000004] = {};long long update(int s, int e, int node, int index, long long dif) { if(s>index || er || e  풀이 : segment tree 핵심은 갱신을 할 때도, 값을 찾을 때도 항상 module 연산을 해주어야 합니다. segment tree에서 update을 하는 방법은 2가지 방법이 존재합니다.1. root에서 말단 노드 순으로 갱신하는 방법 (이 경우 함수는 값을 return 할 필요가 없습니다)2. 말단노드에서 root 순으로 갱신하는 방법 (이 경우 함수는 값을 return 할 필요가 있습니다) 이 때 1번 방식대로 update을 하..

#include int tree[8000008]={};//segment treeint find(int s, int e, int node, int cnt) { //탐색 if(s==e) return s; int m = (s+e)/2; if(tree[node*2]>=cnt) find(s,m,node*2,cnt); else find(m+1,e,node*2+1,cnt-tree[node*2]);}void update(int s, int e, int node, int index, int dif) { //수정 if(index e) return; tree[node] += dif; if(s==e) return; int m = (s+e)/2; update(s,m,node*2,index,dif); update(m+1,e,..

#include #define N 1025int arr[N][N] = {};int tree[N][N*4] = {};int tree2[N*4][N*4] = {};int dif[N*4] = {};int find2(int start, int end, int node, int left, int right, int treeNode) { if(start > right || end right || end index || end index || end  풀이 : 이차원 세그먼트 트리 이차원 세그먼트 트리는, 여러 세그먼트트리들을 말단노드로 취하는 세그먼트트리 입니다.이를 구현하려면 많은 공간이 필요하기 때문에, 범위 수정 문제가 아니라면 펜윅트리로 만드는 것이 효율적입니다. 이차원 세그먼트 트리의 구현은1. 일차..