---
tags: IOICamp
---

# IOICamp Day2 上午 - 資料結構初階

[題目統整](https://vjudge.net/contest/353035) $\mathcal{AND}$ [slide](https://hackmd.io/@xQGCDZGPSKutcn2ux55kvA/ByUQLSlW8#/)

[TOC]

## array 的四種寫法

/// array ///

const int N = 1e6 + 5;
int arr1[N]; // set to 0 by default
int arr2[1'103'255]; // single quote separator (since C++ 14)

fill_n(arr1, N, 1e9);
memset(arr2, 0xab, sizeof(arr2)); // set every byte to 0xab

int arr3[N] = {}; // set to 0 by default

int *ptr1 = arr1, *ptr2 = arr2;
assert(ptr1[0] == 1e9 and ptr2[0] == 0xabababab);
swap(ptr1, ptr2);
assert(ptr2[0] == 1e9 and ptr1[0] == 0xabababab);

ptr1 = new int[N](); // set to 0 by default

/*-----------------------------------------------------------*/
/// std::vector ///

vector<int> v1(N, 100);
auto v2 = v1;

v1.assign(1450145, 0x12345678); // set size to 1450145 and value to 0x12345678
v2.resize(1450145, 0x12345678); // set size to 1450145 and the extended ones set to 0x12345678, others left untouched

swap(v1, v2); // O(1)
v1.swap(v2); // O(1)

/*-----------------------------------------------------------*/
/// std::array ///

array<double, N> a1, a2;
a1.fill(8.7); a2.fill(6.5);

swap(a1, a2); // O(1)

/*-----------------------------------------------------------*/

## stack
- LIFO
- DFS
- 括號匹配

**[例. Largest Rectangle in a histogram (POJ 2559)](http://poj.org/problem?id=2559)**

## queue
- FIFO
- DFS

**[例. Fire! (UVa 11624)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2671)**

## deque
- push_front
- push_back
- pop_front
- pop_back
- 可以取代 stack 或 queue

**[例. 簡單易懂的現代都市 (TIOJ 1566)](https://tioj.ck.tp.edu.tw/problems/1566)**

[\\CSY教我/](https://csy54.github.io/2019/02/TIOJ-1566/)

## priority queue
- 以 binary heap 實作
- Dijkstra's algorithm

**[例. Full Tank? (UVa 11367)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2352)**

## DSU
- maintains a partition of a finite set

**[例. Anansi's Cobweb (Ural 1671)](https://acm.timus.ru/problem.aspx?space=1&num=1671)**

## Segment Tree

一般而言，線段樹都會包含三個主要的 function:
- build
- modify
- query

**[例. Interval Product (UVa 12532)](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3977)**

## Fenwick Tree
- Binary Indexed Tree
- BIT

## Treap