10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서
연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구한다
O(n)
int s = 0,e = 0, ans = 0;
int sum = 0;
while (true) {
if (e == N) {
break;
}
if (sum >= M) {
sum -= arr[s];
s++;
} else {
sum += arr[e];
e++;
}
if (sum == M) {
ans++;
}
}
static int parent[], rank[];
static int find(int u) {
if (u == parent[u]) {
return u;
}
return parent[u] = find(parent[u]);
}
static void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) {
return;
}
// u - > v merging
// tree depth 낮은게 높은 tree로 가야 tree depth가 변하지 않는다
if (rank[u] > rank[v]) {
// cording을 편하게 하기 위해
//swap(u, v);
int temp = u;
u = v;
v = temp;
}
parent[u] = v;
if (rank[u] == rank[v]) {
rank[v]++;
}
}원점 기준으로 벡터 B가 벡터 A의 반시계 방향이면 양수, 시계 방향이면 음수, 평행이면 0을 반환한다
vector cross(vector A, vector B) { //외적
return vector(A.x * B.y - B.x * A.y)
}
double ccw(vector A, vector B) { //원점을 기준으로 CounterClockWise
return cross(A, B)
}
double ccw(vector base, vector A, vector B) { //base를 기준으로 ccw 판단
ccw (A - base, B - base)
}각 정점 삭제후, 컴코넌트 개수 확인 dfs(v) 번 수행 visited에 false인(방문하지 않은 vertex가 있는 지) 확인, 있다면 cut vertex가 존재
### https://www.acmicpc.net/blog/view/12
long long largest(vector<int> &a, vector<int> &tree, int start, int end) {
int n = a.size();
int m = query(a, tree, 1, 0, n-1, start, end);
long long area = (long long)(end-start+1)*(long long)a[m];
if (start <= m-1) {
long long temp = largest(a, tree, start, m-1);
if (area < temp) {
area = temp;
}
}
if (m+1 <= end) {
long long temp = largest(a, tree, m+1, end);
if (area < temp) {
area = temp;
}
}
return area;
}
맨 오른쪽 아래 섬 기준으로 x가 작으면서 y 가 큰것들의 개수 합을 구해가는 문제
문제는 y 좌표가 음/양수로 표현되며 최대 크기가 10^9 이기 때문에 좌표는 압축해줄 필요있다. 압축이란, y의 실제값은 중요하지 않기에 상대적인 값이면된다.
int index= 1;
for( int i = 0; i < pointList.size() ; i ++ ){
Point point = pointList.get(i);
if( i > 0 && point.y != pointList.get(i-1).y ) {
index ++;
}
point.idxY = index;
}https://www.acmicpc.net/problem/3392
Collections.sort(v);
int ans = 0;
int sx = v.get(0).x;
for (int i = 0; i < v.size(); i++) {
ans += (v.get(i).x - sx) * tree[1].sum;
update(v.get(i).yl, v.get(i).yr - 1, 1, 0, MAXY, v.get(i).flag);
sx = v.get(i).x;
}
System.out.println(ans);
}
static void update(int left, int right, int node, int nodeLeft, int nodeRight, int value) {
if (left > nodeRight || right < nodeLeft)
return;
if (left <= nodeLeft && nodeRight <= right)
tree[node].cnt += value;
else {
int mid = (nodeLeft + nodeRight) / 2;
update(left, right, node * 2, nodeLeft, mid, value);
update(left, right, node * 2 + 1, mid + 1, nodeRight, value);
}
if (tree[node].cnt == 0) {
tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
}
else {
tree[node].sum = nodeRight - nodeLeft + 1;
}
}