#define NUM 200000+10 #define o_l (o<<1) #define o_r (o_l+1)
usingnamespace std;
structsgtnode{ int l,r; int swiced; int on,off; sgtnode(){swiced=0;on=0;off=0;} sgtnode(int s,int n,int f): swiced(s),on(n),off(f){} };
// --- input --- int n; vector<int> child[NUM]; // --- Euler tour tree --- int ettIndex2ONorOFF[2*NUM]; int ett_l[NUM]={0}; int ett_r[NUM]={0}; // --- Segment tree --- sgtnode sgmnttr[4*2*NUM];
voidlazydown(int o){ if(sgmnttr[o].swiced == 1){ sgmnttr[o].swiced = 0; swap(sgmnttr[o].on,sgmnttr[o].off); sgmnttr[o_l].swiced ^=1; sgmnttr[o_r].swiced ^=1; } } // --- Segment tree switch --- voidsegswi(int o,int l,int r){ if(sgmnttr[o].l == l and sgmnttr[o].r == r){ sgmnttr[o].swiced ^= 1; return ; } lazydown(o); int mid=(sgmnttr[o].l+sgmnttr[o].r)/2; if(l <= mid) segswi(o_l,l,min(r,mid)); if(r > mid) segswi(o_r,max(l,mid+1),r); // fix o sgmnttr[o].on = (sgmnttr[o_l].swiced?sgmnttr[o_l].off:sgmnttr[o_l].on)+ (sgmnttr[o_r].swiced?sgmnttr[o_r].off:sgmnttr[o_r].on); sgmnttr[o].off = (sgmnttr[o_l].swiced?sgmnttr[o_l].on:sgmnttr[o_l].off)+ (sgmnttr[o_r].swiced?sgmnttr[o_r].on:sgmnttr[o_r].off); } // --- Segment tree query --- intsegqry(int o,int l,int r){ if(sgmnttr[o].l == l and sgmnttr[o].r == r) return sgmnttr[o].swiced?sgmnttr[o].off:sgmnttr[o].on; lazydown(o); int mid=(sgmnttr[o].l+sgmnttr[o].r)/2; int ret=0; if(l <= mid) ret += segqry(o_l,l,min(r,mid)); if(r > mid) ret += segqry(o_r,max(l,mid+1),r); return ret; }
Koyomi is helping Oshino, an acquaintance of his, to take care of an open space around the abandoned Eikou Cram School building, Oshino’s makeshift residence.
The space is represented by a rectangular grid of n × m cells, arranged into n rows and m columns. The c-th cell in the r-th row is denoted by (r, c).
Oshino places and removes barriers around rectangular areas of cells. Specifically, an action denoted by “1 $r_1$ $c_1$ $r_2$ $c_2$” means Oshino’s placing barriers around a rectangle with two corners being ($r_1$, $c_1$) and ($r_2$, $c_2$) and sides parallel to squares sides. Similarly, “2 $r_1$ $c_1$ $r_2$ $c_2$” means Oshino’s removing barriers around the rectangle. Oshino ensures that no barriers staying on the ground share any common points, nor do they intersect with boundaries of the n × m area.
Sometimes Koyomi tries to walk from one cell to another carefully without striding over barriers, in order to avoid damaging various items on the ground. “3 $r_1$ $c_1$ $r_2$ $c_2$” means that Koyomi tries to walk from ($r_1$, $c_1$) to ($r_2$, $c_2$) without crossing barriers.
And you’re here to tell Koyomi the feasibility of each of his attempts.
Input
The first line of input contains three space-separated integers n, m and q (1 ≤ n, m ≤ 2 500, 1 ≤ q ≤ 100 000) — the number of rows and columns in the grid, and the total number of Oshino and Koyomi’s actions, respectively.
The following q lines each describes an action, containing five space-separated integers t, $r_1$, $c_1$, $r_2$, $c_2$ (1 ≤ t ≤ 3, 1 ≤ $r_1$, $r_2$ ≤ n, 1 ≤ $c_1$, $c_2$ ≤ m) — the type and two coordinates of an action. Additionally, the following holds depending on the value of t:
If t = 1: 2 ≤ $r_1$ ≤ $r_2$ ≤ n - 1, 2 ≤ $c_1$ ≤ $c_2$ ≤ m - 1; If t = 2: 2 ≤ $r_1$ ≤ $r_2$ ≤ n - 1, 2 ≤ $c_1$ ≤ $c_2$ ≤ m - 1, the specified group of barriers exist on the ground before the removal. If t = 3: no extra restrictions.
Output
For each of Koyomi’s attempts (actions with t = 3), output one line — containing “Yes” (without quotes) if it’s feasible, and “No” (without quotes) otherwise.
You are given an array of n integers $a_1$ ... $a_n$. The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into k non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.
Input
The first line contains two integers n and k ($2$ ≤ n ≤ $10^5$, 2 ≤ k ≤ min (n, 20)) — the length of the array and the number of segments you need to split the array into.
The next line contains n integers $a_1$, $a_2$, …, $a_n$ (1 ≤ $a_i$ ≤ n) — the elements of the array.
Output
Print single integer: the minimum possible total cost of resulting subsegments.
Examples
input
1 2
7 3 1 1 3 3 3 2 1
output
1
1
input
1 2
10 2 1 2 1 2 1 2 1 2 1 2
output
1
8
input
1 2
13 3 1 2 2 2 1 2 1 1 1 2 2 1 1
output
1
9
Note
In the first example it’s optimal to split the sequence into the following three subsegments: [1], [1, 3], [3, 3, 2, 1]. The costs are 0, 0 and 1, thus the answer is 1.
In the second example it’s optimal to split the sequence in two equal halves. The cost for each half is 4.
In the third example it’s optimal to split the sequence in the following way: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. The costs are 4, 4, 1.
voidclear(){ int i; for(i=0;i<=n;i++){ cnt[i]=0; cntnow[i]=0; } }
booldoaj(int index){ clear(); int l = index == 0?0:divk[index-1]+1; int r = index == k-1?n-1:divk[index+1]; // cout<<index<<":"<<l<<","<<r<<endl; int i; for(i=l;i<=r;i++){ cnt[v[i]]++; // cout<<v[i]<<" "<<cnt[v[i]]<<endl; }