최솟값과 최댓값
그냥 세그먼트 트리로 최소트리, 최대트리 구현하면 끝나는 문제이다.#include#includeusing namespace std;long long arr[100004];long long max_seg[300004],min_seg[300004];int N,M;void max_init(int n, int s, int e){ if(s==e) { max_seg[n] = arr[s]; return; } int m = (s+e)/2; max_init(n*2,s,m); max_init(n*2+1,m+1,e); max_seg[n] = max(max_seg[n*2],max_seg[n*2+1]); return;}long long min_init(int ..
구슬 탈출 2
그냥 간단한 dfs/bfs 문제이다. dfs로 풀어도 되겠지만 10번 이하로 구슬을 빼내야 하는 조건이 있길래 bfs로 풀어봤다.#include#includeusing namespace std;int board[100][100]; //.은 0, #는 1, O는2int N,M;int ans = 0;struct state{ int rx,ry,bx,by,num;};int wx[4]={0,0,1,-1};int wy[4]={1,-1,0,0};queueescape;state mov(int i, state curr){ int bc=0,rc=0; while(board[curr.bx][curr.by]==0) { curr.bx+=wx[i]; curr.by+=wy[i]; ..
구간 합 구하기
중간에 수를 바꾸고 구간 합을 구하는 문제이다.그냥 세그먼트 트리를 쓰면 바로 풀린다.#includeint N, M, K;long long arr[1000004];long long sum[3000004];long long init(int n, int s, int e){ if(s==e) return sum[n] = arr[s]; int m = (s+e)/2; return sum[n] = init(n*2, s, m) + init(n*2+1, m+1, e);}long long fin(int n, int s, int e, int fs, int fe){ if(efe) return 0; if(fse) return; sum[n] += diff; if(s!=e) { ..
