# PythonCP

**Repository Path**: yaoveid/python-cp

## Basic Information

- **Project Name**: PythonCP
- **Description**: python code for competitive programming
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-10-01
- **Last Updated**: 2021-10-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Python Library Code for competitive programming



## 1. Grammar

#### 		1.1 Arrays in python

###### 					1.1.1 How to initialize the array ?

###### 					1.1.2 How to sort the array ?

```python
# sorting basics
values = [2, 5, 1, 4, 3]

# non-decreasing
values.sort()
print(values)

# non-increasing
values.sort(reverse=True)
print(values)

# sorted the origin list doesn't change
print(sorted(values))
print(values)

###########################
# key functions

values = [2, 5, 1, 4, 3]

# evens first
print(sorted(values, key=lambda x: x%2))

values = [(1, 3), (5, 4), (3, 2)]

# sort by the second value
print(sorted(values, key=lambda x: x[1]))

############################
# also key functions

values = [2, 5, 1, 4, 3]

# sort ord by values[i]
# I use it frequently in c++
ord = [i for i in range(5)]
ord.sort(key=lambda i: values[i])
print(ord) # [2, 0, 4, 3, 1]

##########################
# C++ compare, really weird

# returns -1 means x goes first
# x[1] as first key smaller goes first, x[0] as second key bigger goes first
from functools import cmp_to_key
def compare(x, y):
    if x[1] < y[1]:
        return -1
    elif x[1] > y[1]:
        return 1
    if x[0] > y[0]:
        return -1
    elif x[0] < y[0]:
        return 1
    return 0

values = [(1, 3), (5, 4), (3, 2), (1, 2)]
values.sort(key=cmp_to_key(compare))
print(values)

#########################
# overload operator `<` (__lt__)

class pair:
    def __init__(self, _first = 0, _second = 0):
        self.first = _first
        self.second = _second

    def __lt__(self, other):
        if self.second != other.second:
            return self.second < other.second
        return self.first > other.first

    # just for print, like to_string() in c++
    def __str__(self):
        return f'({self.first}, {self.second})'

    __repr__ = __str__

values = [pair(1, 3), pair(5, 4), pair(3, 2), pair(1, 2)]
values.sort()
# why print(values) doesn't work -> add rewrite __repr__
print(values)

```

###### 					1.1.3 How to implement dp ?

###### 					1.1.4 How to get a 2 or 3 dimensional array ?

#### 		1.2 The for-loops

#### 		1.3 "STL" in python

####     	1.4 How to deal with the format

## 2. Specific Algorithms

#### 		2.1 Data structures

###### 				2.1.1 dsu

```python
class DSU:
    # When data[x] < 0, x is a root and -data[x] is its tree size. When data[x] >= 0, data[x] is x's parent.
    data = []
    
    def __init__(self, _n = -1) -> None:
        if _n > 0:
            self.init(_n)
    
    def init(self, _n: int) -> None:
        self.n = _n
        self.data = [-1] * (_n + 1)
        self.components = _n

    def find(self, x: int) -> int:
        if self.data[x] < 0:
            return x

        self.data[x] = self.find(self.data[x])
        return self.data[x]

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)

        if x == y:
            return False

        if (-self.data[x] < -self.data[y]):
            x, y = y, x

        self.data[x] += self.data[x]
        self.data[y] = x
        self.components -= 1
        return True

    def get_size(self, x: int) -> int:
        return -self.data[self.find(x)]

import sys

input = sys.stdin.readline

N, Q = map(int, input().split())
dsu = DSU(N)

while Q > 0:
    Q -= 1

    t, u, v = map(int, input().split())

    if t == 0:
        dsu.unite(u, v)
    else:
        print(int(dsu.connected(u, v)))

```

###### 				2.1.2 fenwick_tree

```python
import sys
input = sys.stdin.readline

# consider to remove assert for better performance
class fenwick_tree:
    def __init__(self, _n):
        self.n = _n
        self.tree = [0] * (_n + 1)

    # index is in [0, n)
    def update(self, index, d):
        assert 0 <= index < self.n
        index += 1
        
        while index <= self.n:
            self.tree[index] += d
            index += index & -index

    # returns the sum of the range[0, p)
    def query(self, p):
        assert p <= self.n
        ret = 0

        while p > 0:
            ret += self.tree[p]
            p -= p & -p

        return ret

    # returns the sum of the range[first, last)
    def query_range(self, first, last):
        return self.query(last) - self.query(first)

N, Q = map(int, input().split())
tree = fenwick_tree(N)

for i, value in enumerate(list(map(int, input().split()))):
    tree.update(i, value)

while Q > 0:
    Q -= 1

    t, a, b = map(int, input().split())

    if t == 0:
        tree.update(a, b)
    else:
        print(tree.query_range(a, b))
```