• E. XKC's basketball team

求比w[i]大m的最远位置。
比赛的时候一直在看B题浪费了很多时间。。（思路也不对。）
维护一个后缀最大值，查找时二分查找后缀最大值大于等于w[i]+m的最右端 


#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
#define INF  0x3f3f3f3f
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
int n,m;
int w[MAXN];
int ww[MAXN];
int main()
{
    s2(n,m);ww[n]=0;
    for(int i=0;i<n;i++) s1(w[i]);
    for(int i=n-1;i>=0;i--) ww[i]=max(w[i],ww[i+1]);
    for(int i=0;i<n;i++)
    {
        int x=w[i]+m,l=i,r=n;
        if(ww[i]<x) 
        {
            printf("-1%c",i==n-1?'\n':' ');
            continue;
        }
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(ww[mid]>=x)
                l=mid+1;
            else 
                r=mid;
        }
        printf("%d%c",l-i-2,i==n-1?'\n':' ');
    }
}

  • B. so easy

给出q次操作，删除某值或者询问某值之后未被删除的第一个值；
n1e9，q1e6
比赛的时候拿分块写当然T掉了，n范围太大了摔。要学会灵活使用STL啊。。
逆向思维还是很重要的，对于每个删除操作存储该值，有两种方法，
一种直接拿set，查找时暴力查找（count函数）
一种用map加并查集的方法，对于每个删除操作更新该点的父亲节点，使每个节点指向他右侧第一个有效点
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
int n,m;
int find_pre(int x){
    if(!mp.count(x)) return x;
    return mp[x]=find_pre(mp[x]);
}
int main(){
    scanf("%d %d",&n,&m);
    int op,x;
    while(m--){
        scanf("%d %d",&op,&x);
        if(op==1)
            mp[x]=find_pre(x+1);
        else{
            x=find_pre(x);
            if(x>n) printf("-1\n");
            else printf("%d\n",x);
        }
    }
    return 0;
}
#第一次知道unordered_map，涨知识了/
map和set差不多都有内置红黑树，就会自动按key值按字典序从小到大排序
 而unordered_map 是采用了哈希函数，没有了排序功能 从名字就看的出来。。。 
但是我们甚至可以用常数的时间进行查找的功能 最坏情况下也才是O(n) 而map的话因为排序了起步都是O(nlogn)