RealDish

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 200010;

int food[N], n, k, d, x, y;

void init_set(){
for(int i = 0; i <= 3 * n; i++)
food[i] = i;
}

int find_set(int x){
return x == food[x] ? x : food[x] = find_set(food[x]);
}

void merge_set(int x, int y){
x = find_set(x);
y = find_set(y);
if( x == y )return ;
food[x] = y;
}

int main(){
cin >> n >> k;
int ans = 0;
init_set();
for(int i = 1; i <= k; i++){
cin >> d >> x >> y;
if(x > n || y > n || x < 1 || y < 1)ans++;
else if(d == 1){
if( find_set(x) == find_set(y + n) || find_set(x) == find_set(y + 2 * n) )ans++;
else{
merge_set(x, y);
merge_set(x + n, y + n);
merge_set(x + 2 * n , y + 2 * n);
}
}else{
if( x == y || find_set(x) == find_set(y) || find_set(x) == find_set(y + n)){
ans++;
}else{
merge_set(x, y + 2 * n);
merge_set(x + n, y);
merge_set(x + 2 * n , y + n);
}
}
}
cout << ans << endl;
return 0 ;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 30010;
int uset[N], b[N],usize[N];

void init_set(){
for(int i = 0 ; i <= N; i++)
{
uset[i] = i;
b[i] = 0;
usize[i] = 1;
}
}

int find_set(int x){
if( x == uset[x] )return x;
int root = find_set(uset[x]);
b[x] += b[uset[x]];
return uset[x] = root;
}

void merge_set(int x, int y){
x = find_set(x);
y = find_set(y);
if(x == y)return;
uset[x] = y;
b[x] = usize[y];
usize[y] += usize[x];
}

int main(){
int t;
scanf("%d\n", &t);
char op; int x, y;
init_set();
while(t--){
op = getchar();
scanf("%d %d\n",&x, &y);
if(op == 'M'){
merge_set(x, y);
}else if(op == 'C'){
int a = find_set(x), c = find_set(y);
if( a == c )cout << abs(b[x] - b[y]) - 1 << endl;
else cout << "-1" << endl;
}
}
return 0;
}


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int N = 2e6 + 10;

int b[N], t, n, c[N],sizec,sizeb,uset[N];
bool flag;
struct node{
int x, y, e;
}a[N];

void discrete(){
sort(c + 1,c + sizec + 1);
for(int i = 1; i <= sizec;i++){
if(i == 1 || c[i] != c[i - 1])
b[++sizeb] = c[i];
}
}

void init_set(){
for(int i = 0 ; i <= sizeb ;i ++)
uset[i] = i;
}

int find_set(int x)
{
return (x == uset[x])? x : uset[x] = find_set(uset[x]);
}

void merge_set(int x, int y){
x = find_set(x);
y = find_set(y);
if( x != y ){
uset[x] = y;
}
}

int query(int x){
return lower_bound(b + 1,b + 1 + sizeb,x) - b;
}

bool cmp(node a, node b){
return a.e > b.e;
}

int main(){
cin >> t;
while(t--){
cin >> n;
sizec = 0, sizeb = 0 ,flag = true;
memset(b, 0,sizeof(b));
memset(c, 0,sizeof(c));
memset(uset,0,sizeof(uset));
memset(a, 0, sizeof(a));
for(int i = 1 ;i <= n;i++){
cin >> a[i].x >> a[i].y >> a[i].e;
c[++sizec] = a[i].x;
c[++sizec] = a[i].y;
}
discrete();
for (int i = 1; i <= n; ++i) {
a[i].x = query(a[i].x);
a[i].y = query(a[i].y);
}
init_set();
sort(a + 1, a + 1 + n, cmp);
for(int i = 1 ;i <= n;i++){
int u = find_set(a[i].x), v = find_set(a[i].y);
if(a[i].e == 1)merge_set(u, v);
else if(u == v){
printf("NO\n");
flag = 0;
break;
}
}
if(flag)printf("YES\n");
}
return 0;
}



/*

*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1000010;
int a[N];
deque<int>windowslide;
int n, k;

void findMin(){
//维护一个单调递减队列， 使得队头始终为滑动窗口的最小值
windowslide.clear();
for(int i = 0; i < n; i++){
while( !windowslide.empty() && a[windowslide.back()] > a[i] )windowslide.pop_back();
//若windowslide不满足单调递增，则弹出队尾元素
while( !windowslide.empty() && i - windowslide.front() >= k )windowslide.pop_front();
//若windowslide已滑过，则弹出队头一个元素
windowslide.push_back(i);//添加元素
if(i >= k - 1)cout << a[windowslide.front()] << ' ' ;//输出
}
}

void findMax(){
//维护一个单调递减队列， 使得队头始终为滑动窗口的最大值
windowslide.clear();
for(int i = 0; i < n; i++){
while( !windowslide.empty() && a[windowslide.back()] < a[i])windowslide.pop_back();
//若windowslide不满足单调递减，则弹出队尾元素
while( !windowslide.empty() && i - windowslide.front() >= k)windowslide.pop_front();
//若windowslide已滑过，则弹出队头一个元素
if(i >= k - 1)cout << a[windowslide.front()] << ' ';//output
}
}

int main(){
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
findMin();//找出滑动窗口的最小值
cout << endl;
findMax();//找出滑动窗口的最大值
}


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 1000010;
int a[N];
deque<int>windowslide;
int n, k;

void findMax(){
windowslide.clear();
for(int i = 0; i < n; i++){
while( !windowslide.empty() && a[windowslide.back()] > a[i] )windowslide.pop_back();
while( !windowslide.empty() && i - windowslide.front() >= k )windowslide.pop_front();
windowslide.push_back(i);
if(i >= k - 1)cout << a[windowslide.front()] << ' ' ;
}
}

void findMin(){
windowslide.clear();
for(int i = 0; i < n; i++){
while( !windowslide.empty() && a[windowslide.back()] < a[i])windowslide.pop_back();
while( !windowslide.empty() && i - windowslide.front() >= k)windowslide.pop_front();
windowslide.push_back(i);
if(i >= k - 1)cout << a[windowslide.front()] << ' ';
}
}

int main(){
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
findMax();
cout << endl;
findMin();
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 100010;
struct node{
LL val;
int dept;
node(){
val = 0; dept = 0;
}
};
struct cmp{
bool operator()(const node a, const node b){
return a.val >  b.val || (a.val == b.val && a.dept > b.dept);
}
};
priority_queue<node, vector<node>, cmp> huffman;
node a[N];
LL ans;
int main(){
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i].val;
huffman.push(a[i]);
}
while((n - 1)%(k - 1)!=0){
node b;
huffman.push(b);
n++;
}
while(huffman.size() > 1){
node mid; int dp;
for(int i = 0; i < k; i++){
mid.val += huffman.top().val;
dp = max(dp, huffman.top().dept);
huffman.pop();
}
mid.dept = dp + 1;
huffman.push(mid);
ans += mid.val;
}
cout << ans << '\n' << huffman.top().dept << endl;
return 0;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int N = 10010;
typedef pair<int, int> PII;

int main(){
int n;
while(cin >> n){
vector<PII> products(n);
for(int i = 0; i < n; i++){
cin >> products[i].second >> products[i].first;
}
sort(products.begin(), products.end());
priority_queue<int,vector<int>, greater<int> > heap;
for(auto goods : products){
heap.push(goods.second);
if(heap.size() > goods.first)heap.pop();
}
int ans = 0;
while(!heap.empty()){
ans += heap.top();
heap.pop();
}
cout << ans << endl;
}
}


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 100010, M = 4e6 + 50;
int son[M][2], a[N], idx;
int u, v, w;

void insert(int x){
int p = 0;
for(int i = 30; ~i; i--){
int &s = son[p][x >> i & 1];
if(!s) s = ++idx;
p = s;
}
}

int query(int x){
int p = 0, cnt = 0;
for(int i = 30; ~i; i--){
int s = x >> i & 1;
if(son[p][!s]){
cnt += 1 << i;
p = son[p][!s];
}else p = son[p][s];
}
return cnt;
}

int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> u >> v >> w ;
a[v] = a[u] ^ w;
}
for(int i = 0; i < n; i++){
insert(a[i]);
}
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans, query(a[i]));
}
cout << ans << endl;
}


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int N = 100010, M = 4000050;
int pos;
int son[M][2], a[N];

void insert(int x){
int p = 0;
for(int i = 30; ~i; i--){
int &s = son[p][x >> i & 1];
if(!s)s = ++pos;
p = s;
}
}

int query(int x){
int p = 0, res = 0;
for(int i = 30; ~i; i--){
int s = x >> i & 1;
if(son[p][!s]){
res += 1 << i;
p = son[p][!s];
}else p = son[p][s];
}
return res;
}

int main(){
int n, ans = 0;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
insert(a[i]);
}
for(int i = 1; i <= n; i++){
ans = max(ans, query(a[i]));
}
cout << ans << endl;
return 0;
}


/*

1、朴素方法：

2、差分序列：

*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

const int N = 10010;//牛的最多多少个
int c[N];//牛的差分序列
map<pair<int,int>, bool>existed;//判断关系对是否存在重复

int main(){
int n, p, h, m;
cin >> n >> p >> h >> m;
memset(c, 0, sizeof(c));
for(int i = 1; i <= m; i++){
int a, b;
cin >> a >> b;
if(a > b)swap(a , b);//保证a比b小，即(a, b)是有效的
if(existed[make_pair(a, b)])continue;//若关系对之前已判断则不需要再处理
c[a + 1]--, c[b]++;//处理c[i + 1 ~ j - 1]的牛
existed[make_pair(a, b)] = true;
}
for(int i = 1; i <= n; i++){
c[i] += c[i - 1];
cout << h + c[i] << endl;
}
return 0;
}