CheaSim Blog
发表更新acm模板1 分钟读完 (大约166个字)

求逆元和组合数模板

求逆元

$O(n)$求逆元

1
2
3
4
ll inv[maxn];
inv[1] = 1;
rep(i,2,maxn) 
    inv[i] = inv[mod%i] * (mod-mod/i) % mod;

$O(n)$求阶乘

1
2
3
4
ll f[maxn];
ll f[1] = 1;
rep(i,2,maxn)
    f[i] = f[i-1]*i;

求$n\choose k$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll cur,p[maxn],q[maxn],inv[maxn];
ll C(ll n,ll k){
    return p[n]*q[k]%mod*q[n-k]%mod;
}
ll c(ll n,ll k){
    if(n<maxn) return C(n,k);
    if(!k) return 1;
    return cur = cur*inv[k]%mod*((n-k+1)%mod)%mod;
}
void init(){
    p[0]=p[1]=q[0]=q[1]=inv[0]=inv[1]=1;
    for(ll i = 2;i<maxn;i++){
        inv[i] = (mod-mod/i)*inv[mod%i]%mod;
        q[i] = q[i-1] * inv[i] % mod;
        p[i] = p[i-1] * i % mod;
    }
}
//在每次的时候就得cur初始化为1

求$A^k_n$

1
2
3
int A(int n,int k){
    return c(n,k)*p[k]%mod;
}
发表更新acm2 分钟读完 (大约260个字)

[POJ3264]Balanced Lineup

[POJ3264]Balanced Lineup

题意

给一个数列，求数列中$l,r$范围内最大值和最小值的差。

题解

st表模板题。求两次rmq即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
int n,q;
int st[maxn][32-__builtin_clz(maxn)];
int st2[maxn][32-__builtin_clz(maxn)];
int h[maxn];
int ST(){
    int l = 31 - __builtin_clz(n);
    rep(i,0,n) {st[i][0] = h[i];st2[i][0] = h[i];}
    rep(j,0,l) rep(i,0,n-(1<<j)+1){
        st[i][j+1] = max(st[i][j],st[i+(1<<j)][j]);
        st2[i][j+1] = min(st2[i][j],st2[i+(1<<j)][j]);
    }
}
int max_rmq(int l,int r){
    int k = 31 - __builtin_clz(r-l+1);
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
int min_rmq(int l,int r){
    int k = 31 - __builtin_clz(r-l+1);
    return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
int main(){
#ifdef LOCAL
    freopen("shui.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&q)){
    rep(i,0,n) scanf("%d",&h[i]);
    ST();
    while(q--){
        int l,r;scanf("%d%d",&l,&r);
        l--,r--;
        printf("%d\n",max_rmq(l,r)-min_rmq(l,r));
    }
    }
    return 0;
}

发表更新acm4 分钟读完 (大约604个字)

2018 Multi-University Training Contest 8 D.Parenth

2018 Multi-University Training Contest 8 D.Parentheses Matrix

传送门

题目大意

一个由左括号和右括号组成的矩阵，定义矩阵的权值是矩阵中匹配的行数和列数的和。

题解

一道比较典型的构造题。

如果行数或者列数是奇数那么矩阵显然是奇数的行或列匹配不了。

(())

(())

(())

当情况很多有两个变量的时候我们可以假设一个变量小于另一个变量，假设$h\leq m$。

构造过程还是题解比较清晰。

首先，第一行、最后一列中最多只有一个能够匹配，第一列、最后一行也只有一个能够匹配（考 虑右上角和左下角的括号选取方法），故答案不会超过 w+h−2。 当 h = 2 时，每一列可以构造一对匹配，这样答案已经到达上界。 当 h = 4 时，可以如下构造：

( ( ( ( ( (

) ) ) ) ) )

( ( ( ( ( (

) ) ) ) ) )

这样答案是 w+h−3。

若存在更优的答案，则必有一个边界能够匹配，不妨设是第一列。这样，就已 经有除第一行以外的两行（右括号开头的行）不匹配了，而第一行和最后一列中至少有一个不匹配， 因此最优解不会超过 w+h−3。

当 h≥6 时，可以如下构造：

( ( ( ( ( ( ( (

( ) ( ) ( ) ( )

( ( ) ( ) ( ) )

( ( ( ( ) ) ) )

( ( ) ( ) ( ) )

) ) ) ) ) ) ) )

答案是 w+h−4。同理可证明不存在更优的方法。

在实际操作的时候如果$h>m$可以将矩阵反转一下。就ok了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int t,h,w;
char g[300][300];
int main(){
#ifdef LOCAL
    freopen("d.in","r",stdin);
#endif
    scanf("%d",&t);
    while(t--){
        bool flag = 0;
        scanf("%d%d",&h,&w);
        if(h&1){
            rep(i,0,h){
                rep(j,0,w){
                    g[i][j] = (j<w/2 ? '(' : ')');
                }
            }
        }else if(w&1){
            rep(i,0,h){
                rep(j,0,w){
                    g[i][j] = (i<h/2 ? '(' : ')');
                }
            }
        }
        else{
            if(h>w){
                int temp = h;
                h = w;
                w = temp;
                flag = 1;
            }
            if(h==2){
                rep(i,0,w){
                    g[0][i] = '(';
                    g[1][i] = ')';
                }
            }else if(h == 4){
                rep(i,0,w){
                    g[0][i] = '(';
                    g[1][i] = (i<w/2 ? ')' : '(');
                    g[2][i] = (i<w/2 ? '(' : ')');
                    g[3][i] = ')';
                }
            }else{
                rep(i,0,h){
                    rep(j,0,w){
                        if(i==0 || j==0) g[i][j] = '(';
                        else if(i == h-1 || j == w-1) g[i][j] = ')';
                        else if((i^j)&1) g[i][j] = ')';
                        else g[i][j] = '(';
                    }
                }
            }
        }
        if(flag){
            rep(j,0,w){
                rep(i,0,h){
                    putchar(g[i][j]);
                }
                puts("");
            }
        }else{
            rep(i,0,h){
                rep(j,0,w){
                    putchar(g[i][j]);
                }
                puts("");
            }
        }
    }
    return 0;
}

发表更新acm3 分钟读完 (大约514个字)

A. Rikka with Nash Equilibrium

A. Rikka with Nash Equilibrium

题解：

神仙dp题

将数字从大到小一次排列，从大往小取.

  • 构造一个三维$dp[now][j][k]​$,表示放入$now​$数字的时候有$i​$行和$j​$列有数字下的情况。为了防止数字成为平衡位置，每次放置的位置都要放置在之前放置元素所在的列或者行上，如果不这么放置的话，他就会成为剩下当前行和当前列最大的(就没能有比他大的数字了)。

  • 初始化，因为第一个数字可以任意存放所以$dp[0][1][1]=m*n$。

  • 转移方程:

    1. 该点放置位置上行和列都有元素，那就是有$i$列和$j$行可以存放。剩下的位置是$j*k-i+1$

      ，$dp[next][j][k]+=dp[now][j][k]*(jk-i+1)$

    2. 该点放置位置上列已经有元素了，但是行上没有元素，从位置的行数减一转移加了一行$dp[next][j][k]+=dp[now][j-1][k]*j(n-i+1)$

    3. 同理如果行有元素的话。$dp[next][j][k]+=dp[now][j][k-1]*i(m-j+1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 88;
int t,m,n;
ll mod;
ll dp[2][maxn][maxn];
inline ll add(ll a, ll b){
    return (a+b>mod)?(a+b)%mod:a+b;
}
inline ll mul(ll a,ll b){
    return a*b>mod?(a*b)%mod:a*b;
}
int main(){
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%lld",&n,&m,&mod);
        memset(dp,0,sizeof(dp));
        dp[0][1][1] = n*m;
        int now = 0;
        rep(i,2,m*n+1){
            int nxt = now^1;
            memset(dp[nxt],0,sizeof(dp[nxt]));
            rep(j,0,n+1){
                rep(k,0,m+1){
                    if(dp[now][j][k]){
                        ll tot = j*k - i + 1;
                        dp[nxt][j][k] = add(dp[nxt][j][k],dp[now][j][k]*tot);
                        dp[nxt][j+1][k] = add(dp[nxt][j+1][k],mul(dp[now][j][k],1ll*k*(n-j)));
                        dp[nxt][j][k+1] = add(dp[nxt][j][k+1],mul(dp[now][j][k],1ll*j*(m-k)));
                        //cout<<dp[now][j][k];
                    }
                }
            }
            now = nxt;
        }
        printf("%lld\n",dp[now][n][m]);
    }
    return 0;
}

发表更新学习笔记2 分钟读完 (大约228个字)

ST表学习笔记

ST表学习笔记

功能

ST表示用来求解给定区间RMQ的最值问题。

预处理复杂度:$O(nlongn)$，查询复杂度$O(1)$。

详解

原理

将原数组分成以2幂次的区间块，用$mn[i][j]$表示从$j$到$j-2^i-1$的最小值，最小值显然等于$$min(前半段最小值,后半段中最小值)$$从而得到递推式子

$$min[i][j]=min(mn[i-1][j],mn[i-1][j+2^{i-1}])$$

预处理代码

1
2
3
4
5
6
7
8
9
p[0] = 1;
rep(i,1,20) p[i] = 1<<i;
Log[0] = -1;
rep(i,1,200000) Log[i] = Log[i/2] + 1;
rep(i,1,n) mn[0][i] = a[i];
rep(i,1,n+1)
    rep(j,1,n+1)
    	if(j+p[i]-1 <= n)
            mn[i][j] = min(mn[i-1][j],mn[i-1][j+p[i-1]]);

查询

定理1:$$2^{log(a)}>a/2$$

查询$x$到$y$的最小值可以假设$len=y-x+1,t=log(len)$，根据定理1，$2^t>len/2$，那么位置过了一半之后最小值的可能就落在了$x$后面的$2^t$和$y$前面的$2^t$。式子为$$mmin = min(mn[t][x],mn[t][y-2^t+1])$$

实现

1
2
int t = Log[y-x+1];
int ans = min(mn[t][x],mn[t][y-p[t]+1]);

Reference:https://blog.csdn.net/hanks_o/article/details/77547380

发表更新acm5 分钟读完 (大约685个字)

杭电多校Age_of_Moyu

Age of Moyu

题解

标程的set+bfs貌似有漏洞。

1
2
3
4
5
6
7
5 6
1 2 1
2 3 1
3 4 1
4 5 1
1 3 2
1 4 3

这个数据就可以hack掉了。

所以我果断copy了dls队伍的代码。(用边做)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
inline char inputchar()
{
    return getchar();
}
inline void inputnum(int &ret)
{
    char ch = inputchar();
    while(ch < '0' || ch > '9')
        ch = inputchar();
    ret = ch - '0';
    ch = inputchar();
    while(ch >= '0' && ch <= '9')
    {
        ret = ret * 10 + ch - '0';
        ch = inputchar();
    }
}
const int MAXN = 101010, MAXM = 202020;
int n, m;
class Edge
{
public:
    int to, c, next;
}e[MAXM * 2];
int en, head[MAXN];
int dis[MAXM];
deque<int> q;
void insert()
{
    int u, v, c;
//    scanf("%d%d%d", &u, &v, &c);
    inputnum(u);
    inputnum(v);
    inputnum(c);
    e[++en].to = v;
    e[en].c = c;
    e[en].next = head[u];
    head[u] = en;
    e[++en].to = u;
    e[en].c = c;
    e[en].next = head[v];
    head[v] = en;
}
bool solve()
{
    if(scanf("%d%d", &n, &m) != 2)
        return false;
    memset(head, -1, (n + 2) * sizeof(int));
    en = 1;
    for(int i = 1; i <= m; i++)
        insert();
    memset(dis, 1, (m + 2) * sizeof(int));
    for(int i = head[1]; i > 0; i = e[i].next)
        dis[i / 2] = 1, q.push_back(i / 2);
    while(!q.empty())
    {
        int now = q.front();
        q.pop_front();
        for(int i = head[e[now * 2].to]; i > 0; i = e[i].next)
            if(e[i].c == e[now * 2].c)
            {
                if(dis[i / 2] > dis[now])
                    dis[i / 2] = dis[now], q.push_front(i / 2);
            }
            else
            {
                if(dis[i / 2] > dis[now] + 1)
                    dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
            }
        for(int i = head[e[now * 2 + 1].to]; i > 0; i = e[i].next)
            if(e[i].c == e[now * 2 + 1].c)
            {
                if(dis[i / 2] > dis[now])
                    dis[i / 2] = dis[now], q.push_front(i / 2);
            }
            else
            {
                if(dis[i / 2] > dis[now] + 1)
                    dis[i / 2] = dis[now] + 1, q.push_back(i / 2);
            }
    }
    int ans = MAXM;
    for(int i = head[n]; i > 0; i = e[i].next)
        if(ans > dis[i / 2])
            ans = dis[i / 2];
    if(ans == MAXM)
        ans = -1;
    printf("%d\n", ans);
    return true;
}
int main()
{
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    while(solve());
    return 0;
}

时间卡的非常紧。优化了很多终于2.4s过了。

$$O(n^2)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
void read(int &x){
	char ch = getchar();x = 0;
	for (; ch < '0' || ch > '9'; ch = getchar());
	for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 1e5 + 10;
int n,m,ans,cnt;
int head[maxn],dis[maxn<<1];
struct Edge{
    int to,next,idx;
}G[maxn<<2];
void add(int u,int v,int id){
    G[cnt].to = v;
    G[cnt].next = head[u];
    G[cnt].idx = id;
    head[u] = cnt++;
}
deque<int> q;
void bfs(){
    for(int i = head[1];~i;i=G[i].next) dis[i/2] = 1,q.push_back(i/2);
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        for(int i = head[G[now*2].to];~i;i=G[i].next){
            if(G[i].idx == G[now*2].idx){
                if(dis[i/2] > dis[now]){
                    dis[i/2] = dis[now];q.push_front(i/2);
                }
            }else{
                if(dis[i/2] > dis[now] + 1){
                    dis[i/2] = dis[now]+1;q.push_back(i/2);
                }
            }
        }
        for(int i = head[G[now*2+1].to];~i;i=G[i].next){
            if(G[i].idx == G[now*2+1].idx){
                if(dis[i/2] > dis[now]){
                    dis[i/2] = dis[now];q.push_front(i/2);
                }
            }else{
                if(dis[i/2] > dis[now]+1){
                    dis[i/2] = dis[now]+1;q.push_back(i/2);
                }
            }
        }
    }
    ans = INF;
    for(int i = head[n];~i;i=G[i].next){
        if(ans > dis[i/2]) ans = dis[i/2];
    }
}
int main(){
#ifdef LOCAL
    freopen("a.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&m)){
        memset(head,-1,sizeof(int)*(n+2));cnt = 0;
        rep(i,0,m+2) dis[i] = INF;
        rep(i,0,m){
            int u,v,id;read(u);read(v);read(id);
            add(u,v,id);add(v,u,id);
        }
        bfs();
        printf("%d\n",ans==INF?-1:ans);
    }
    return 0;
}
发表更新acm4 分钟读完 (大约579个字)

Appleman_and_Tree

Appleman and Tree

链接

如果觉得我的题解看不懂可以去看 大佬的题解

题目大意

将一颗树节点染成白色或者黑色，减去几条变使得每个联通分支都有一个黑色节点，问有多少种减边方案。

题解

树状dp+dfs

下次看到两种状态加点的。dp应该想到用2维。

  1. 定义$dp[i][j]$表示点$i$在以点$i$为根的子树去掉点$i$所在的联通快有黑点$1$和无黑点$0$的方案数
  2. 假设点$u$，首先如果$u$是黑色，那么$$dp[i][1]=1$$，否则$dp[i][0]=1$。
    1. 点$u$加入一个子树$v$。假设原来$u$没有黑点。
      1. 如果加入的$v$是有黑点的，有两种选择，切断边$u$还是没有黑点，方案数$dp[u][0]=dp[u][0]*dp[v][1]$，不切断边$u$就产生了黑点$dp[u][1]=dp[u][0]*dp[v][1]$
      2. 如果加入的$v$是无黑点的，只能选择不切断。方案数$dp[u][0]=dp[u][0]*dp[v][0]$
    2. 点$$u$$加入一个子树$v$。假设原来$u$有黑点。
      1. 如果加入的$v$是有黑点的，只能选择切断，方案数$dp[u][1]=dp[u][1]*dp[v][1]$
      2. 如果加入的点$v$是无黑点的，只能选择切断，因为不能产生无黑点的联通分支，方案数$dp[u][1]=dp[u][1]*dp[v][0]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
struct node{
    int to,next;
}G[maxn<<1];
int cnt;
ll dp[maxn][2];
int head[maxn];
void add(int from,int to){
    G[cnt].to = to;
    G[cnt].next = head[from];
    head[from] = cnt++;
}
int n;
void dfs(int u,int fa){
    for(int i = head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v == fa) continue;
        dfs(v,u);
        dp[u][1] = dp[u][1]*dp[v][1]%mod + dp[u][0]*dp[v][1]%mod + dp[u][1]*dp[v][0]%mod;
        dp[u][1] %= mod;
        dp[u][0] = dp[u][0]*dp[v][0]%mod + dp[u][0]*dp[v][1]%mod;
        dp[u][0] %= mod;
    }
}
int main(){
#ifdef LOCAL
    freopen("B.in","r",stdin);
#endif
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    rep(i,1,n){
        int v; scanf("%d",&v);
        add(i,v);add(v,i);
    }
    rep(i,0,n){
        scanf("%d",&dp[i][1]);
        if(dp[i][1]==0) dp[i][0] = 1;
    }
    dfs(0,-1);
    cout<<dp[0][1]<<endl;
    return 0;
}
发表更新acm模板几秒读完 (大约100个字)

逆元模板

求逆元模板

递推求逆元

1
2
3
4
5
int inv[maxn];
int inv[1] = 1;
rep(i,2,max){
    inv[i] = inv[mod%i]*(mod-mod/i)%mod;
}

费马小定理求逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll extend_gcd(ll a,ll b,ll x,ll y){
    if(a==0 && b==0) return -1;
    if(b==0) {
        x = 1;y = 0;
        return a;
    }
    ll d = extend_gcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}
ll mod_reverse(ll a,ll n){
    ll x,y;
    ll d = extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
发表更新cf15004 分钟读完 (大约530个字)

codeforcesPoints

codeforcesPoints

题意

给出几个点，让你求出在某个点的右边和上面最接近他的点是哪一个点。

题解

线段树+set应用

对$x$进行离散化处理，对于每一个$x$进行建一个set，用线段树维护$x$之间的$y$的最大值。对于给出点的右上点，我们可以用二分来set搜索，还有在线段树中优先搜索左边靠近给出点的点。

这是我第一次看到离散化的线段树应用。哭泣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
inline int Max(int a,int b){return a>b?a:b;}
//head
const int maxn = 2e5 + 20;
int maxy[maxn<<2],mark[maxn],x[maxn],y[maxn];
set<int> s[maxn];
int n,m;
char op[20];
vector<int> v;
void build(int l,int r,int rt){
    if(l==r){
        maxy[rt] = -1;
        return;
    }else{
        int mid = (l+r)>>1;
        build(lson);
        build(rson);
    }
}
void pushup(int rt){
    maxy[rt] = Max(maxy[rt<<1],maxy[rt<<1|1]);
}
void update(int pos,int val,int l,int r,int rt){
    if(l==r){
        maxy[rt] = val;
        return;
    }
    int mid = (l+r)>>1;
    if(pos <= mid) update(pos,val,lson);
    else update(pos,val,rson);
    pushup(rt);
}
int query(int L,int R,int val,int l,int r,int rt){
    if(maxy[rt] <= val) return -1;
    if(l==r) return l;
    int mid = (l+r)>>1;
    int ans = -1;
    if(L <= mid && maxy[rt<<1] > val){
        ans = query(L,R,val,lson);
        if(ans != -1) return ans;
    }
    if(R > mid && maxy[rt<<1|1] > val)
        ans = query(L,R,val,rson);
    return ans;
}
int main(){
#ifdef LOCAL
    freopen("points.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,n){
        scanf("%s%d%d",op,&x[i],&y[i]);
        if(op[0] == 'a') mark[i] = 1;
        else if(op[0] == 'r') mark[i] = 2;
        else mark[i] = 3;
        if(op[0] == 'a') v.push_back(x[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m = v.size();
    rep(i,0,n){
        if(mark[i] == 1 || mark[i] == 2){
            int pos = lower_bound(v.begin(),v.end(),x[i]) - v.begin()+1;
            if(mark[i] == 1) s[pos].insert(y[i]);
            else s[pos].erase(y[i]);
            int val;
            if(s[pos].empty()) val = -INF;
            else val = *(--s[pos].end());
            update(pos,val,1,m,1);
        }else{
            int pos = upper_bound(v.begin(),v.end(),x[i]) - v.begin()+1;
            int z = query(pos,m,y[i],1,m,1);
            if(z == -1 || pos == m+1){
                puts("-1"); continue;
            }
            int ans = *(s[z].upper_bound(y[i]));
            printf("%d %d\n",v[z-1],ans);
        }
    }
    return 0;
}
关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×