rofn123

#include #include int tree[266000] = {}, ETT=0;typedef struct list { //단뱡향 리스트 struct list * next; int val; }list;void insert(int x, int y, list vec[]) { //리스트 삽입 list * newNode = (list*) malloc(sizeof(list)); newNode->val = y; newNode->next = vec[x].next; vec[x].next = newNode; return;}void dfs(int x, int start[], int end[], list vec[]) { //ETT start[x] = ++ETT; for(list *p = vec[x].next; p!=NU..

#include #include int ETT = 0; //오일로 경로 트릭을 위한 변수int tree[266000]={}, lazy[266000]={}, arr[100001]={}; //lazy propagationtypedef struct list{ //리스트 자료구조를 위한 구조체 struct list * prev; struct list * next; int val;}list;void insert(int s, int val, list vec[]) { //리스트에 삽입 list * newNode = (list*) malloc(sizeof(list)); newNode->val = val; newNode->next = vec[s].next; newNode->prev ..

#include #include int tree[266000]={},lazy[266000]={}; //lazy propagationint ETT = 0; //오일러 경로 트릭에 사용할 변수typedef struct list { //리스트를 구성할 노드의 구조체 struct list * prev; struct list * next; int val;} list;void insert(int sup, int sub, list vec[]) { //리스트 삽입 list *newNode = (list*) malloc(sizeof(list)); newNode->val = sub; newNode->prev = vec+sup; newNode->next = vec[sup].next; ..

#include #define swap(x,y) {int t=x;x=y;y=t;} //치환int tree[262150]={}; //10만인 경우 2.6215 을 곱해도 ㄱㅊ은 것 같습니다. 400000으로 잡아도 됩니다.int lazy[262150]={};int init(int s, int e, int node) { //트리를 1번째 색깔로 칠해져 있도록 초기화 if(s==e) return tree[node] = 1; int m=(s+e)/2; return tree[node] = init(s,m,node*2) | init(m+1,e,node*2+1);}void lazyU(int s, int e, int node) { //미룬거 업데이트 if(lazy[node]) { tree[node] = lazy[no..

#include int tree[400004] = {};int lazy[400004] = {};void lazyUpdate(int s, int e, int node) { //미룬거 처리 if(lazy[node]) { tree[node] += (e-s+1) * lazy[node]; if(s!=e) { lazy[node*2] += lazy[node]; lazy[node*2+1] += lazy[node]; } } lazy[node] = 0; return;}void update(int s, int e, int node, int l, int r, int dif) { //구간 수정 lazyUpdate(s,e,node); if(s>r || eindex || e 풀이 : 느리게 갱신되는 세그먼트 트리, l..

#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 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..