【牛客小白月赛24】补题（离散化，树剖）TODO

这次比赛啥都不说了===心酸。
这次小白赛难度其实不高，除了A之外我应该都能做出来才对===心酸
FG很简单，不写题解了。A放弃了--

H 好朋友——并查集+离散化

先把所有朋友关系合并到并查集里面；然后枚举敌人关系，只要两者在一个朋友集合里面就是矛盾的。
当时只用了并查集没过，想着10^9数值的话tree数组直接用map，但是map本身内部有排序，处理速度不如数组，导致时间超时
这道题数据设计的比较强。。。只能离散化，离散化就是把一组数去重排序之后映射成下标，即

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e6 + 5;
const int N = 1e9+1;
int parent[MAXN];
//map<int,int> parent;
int find(int i) { 
    if (parent[i] != i) parent[i] = find(parent[i]);
    return parent[i];
}

void uni(int x, int y)
{
  int rootx = find(x);
  int rooty = find(y);
  if (rootx != rooty)
  {
    parent[rooty] = rootx;
  }
}

int a[MAXN],b[MAXN],c[MAXN];
vector<int> d;
signed main()
{
    int t;cin>>t;
    while(t--){
        d.clear();
        int n;cin>>n;
        for(int i=1;i<=n*2;++i) parent[i]=i;
        for(int i=0;i<n;++i){
            scanf("%d %d %d",&a[i],&b[i],&c[i]);
            d.push_back(a[i]);
            d.push_back(b[i]);
        }
        sort(d.begin(), d.end());
        d.erase(unique(d.begin(),d.end()),d.end());
        for (int i = 0; i < n; ++i) {
            a[i] = lower_bound(d.begin(), d.end(), a[i]) - d.begin() + 1,
            b[i] = lower_bound(d.begin(), d.end(), b[i]) - d.begin() + 1;
        }

        bool flag=false;
        for(int i=0;i<n;++i){
            if(c[i]==1){
                uni(a[i],b[i]);
            }
        }
        for(int i=0;i<n;++i){
           if(c[i]==0){
                int rootx = find(a[i]);
                int rooty = find(b[i]);
                if (rootx == rooty) {
                    cout<<"NO"<<endl;
                    flag=true;
                    break;
                }
            }
        }
        if(!flag) cout<<"YES"<<endl;
    }
    return 0;
}

I 求和--dfs重新编号

已知有 n个节点，有 n−1 条边，形成一个树的结构。
给定一个根节点 k，每个节点都有一个权值，节点i的权值为 vi​。
给 m个操作，操作有两种类型：
1 a x ：表示将节点 a的权值加上 xxx
2 a ：表示求 a 节点的子树上所有节点的和（包括 a 节点本身）

本来想直接暴力，每次查询直接dfs求距离---超时

void dfs(int u,int father){
    sum[u]=num[u];
    for(int i=h[u];i;i=ne[i])if(p[i]!=father){
        dfs(p[i],u);
        sum[u]+=sum[p[i]];
    }
}

想了想，这种动态单点修改求区间和难道不是树状数组和线段树吗？
但是树状数组要从1开始并且连续区间和阿。——自然也就想到利用dfs对整棵树重新编号，编号后，可以使得任意一颗子树的序号连续

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MAXN = 1e6 + 5;
#define N 1000005
int tree[MAXN]={0};
int MAXNTREE;
inline long long query(int pos)
{
    long long ans = 0;
    while (pos > 0) {
        ans+=tree[pos];
        pos -= pos & (-pos);
    }
    return ans;
}
inline void update(int pos, int val)
{
    int ans = 0;
    while (pos <= MAXNTREE) {
        tree[pos]+=val;
        pos += pos & (-pos);
    }
}
ll tot,dis[N],fa[N],h[N],ne[N<<1],p[N<<1],wi[N<<1];
void addEdge(int u,int v,int w){p[++tot]=v;ne[tot]=h[u];h[u]=tot;wi[tot]=w;}
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
void addOrEdge(int u,int v){ne[++tot]=h[u];h[v]=tot;}
ll num[MAXN];ll siz[MAXN]={0};
ll no[MAXN];//重新编号使得子树的节点号连续
int g_cnt=0;
void dfs(int u,int father){
    no[u]=++g_cnt;
    siz[u]=1;
    for(int i=h[u];i;i=ne[i])if(p[i]!=father){
        dfs(p[i],u);
        siz[u]+=siz[p[i]];
    }
}

signed main()
{
    int n,m,rt;cin>>n>>m>>rt;
    tot=0;
    MAXNTREE=n;
    int sum=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(rt,0);
    for (int i = 1; i <= n; ++i) update(no[i], num[i]);
    for(int i=1;i<=m;++i){
        int x,u,w; scanf("%d",&x);
        if(x==1){
            scanf("%d %d",&u,&w);
            update(no[u],w);
        }else{
            scanf("%d",&u);
            printf("%lld\n", query(no[u] + siz[u] - 1) - query(no[u] - 1));
        }
    }
    return 0;
}

J 求和——前缀和

这个是真的秀。。。我太菜了 只想到了没想到可以用前缀和来算

#include <bits/stdc++.h>
#define ll long long
const int MAXN = 500005;
using namespace std;
ll a[MAXN], sum[MAXN];
const int MOD = 1e9 + 7;
int main()
{
    int n;
    scanf("%d", &n);
    assert(1 <= n && n <= 500000);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        sum[i] = (sum[i - 1] + a[i]) % MOD;
        ans = (ans + a[i] * a[i]) % MOD;
    }
    ans = (n - 1LL) * ans % MOD;
    for (int i = 1; i <= n; i++)
        ans = (ans - 2LL * a[i] * sum[i - 1] % MOD + MOD) % MOD;
    printf("%lld\n", ans);
}

B 组队——二分

比较简单。先排序，每个数num[i]二分找到第一个大于等于num[i]+k的数位置，两者下标相减就是能取到的数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int MAXN = 5e5 + 10;
int num[MAXN];
map<int,int> has;
signed main()
{
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;++i){
            cin>>num[i];
        }
        sort(num,num+n);
        int l=1,r=n;
        int ans=0;
        for(int i=0;i<n;++i){
           int x = lower_bound(num+i+1,num+n,num[i]+k)-num;
            //cout<<x<<endl;
            if(num[x]==num[i]+k){
                ans=max(ans,x-i+1);
            }else{
                ans=max(ans,x-i);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}