A simple Blog for wyx I've been down the bottle hoping.
4399: 魔法少女LJJ
发表于: | 分类: Oi | 评论:0 | 阅读:141

仔细看操作数,然后你就会感叹:这题是来逗比的吧…………

对于这七个操作

操作1 新建一棵权值线段树,更新对应的信息
操作2 权值线段树合并即可
操作3 清空$<x$的部分,并把信息更新到$x$上
操作4 清空$>x$的部分,并把信息更新到$x$上
操作5 直接查找就成
操作6 转化为$\log$的加法
操作7 并查集求$size$

注意清空的时候把对应的标号标成0,然后处理一下就行了

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double f2;
const int N = 4e5+5;
const int M = 20 * N;
const int Max = 1000000000;

int size[N], fa[N], val[N];
int m, c, sz, cnt, root[N];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

inline int find(int x) {
    return fa[x] ^ x ? fa[x] = find(fa[x]) : fa[x];
}

double tr[M];
int ls[M], rs[M], sum[M];

void insert(int &k,int l,int r,int val,double e) {
    k = ++sz; sum[k] = 1, tr[k] = e;
    if(l==r) return;
    int mid = (l+r) >> 1;
    if(val <= mid) insert(ls[k],l,mid,val,e);
    else insert(rs[k],mid+1,r,val,e);
}

void merge(int &x,int y,int l,int r) {
    if(!x || !y) {
        x += y; return ; 
    }
    if(l == r) {
        sum[x] += sum[y];
        tr[x] += tr[y];
        return;
    }
    int mid = (l+r) >> 1;
    merge(ls[x],ls[y],l,mid);
    merge(rs[x],rs[y],mid+1,r);
    sum[x] = sum[ls[x]] + sum[rs[x]];
    tr[x] = tr[ls[x]] + tr[rs[x]];
}

void change1(int &k,int l,int r,int lmt,int val) {
    if(!k) k = ++sz;
    if(l==r) {
        sum[k] += val;
        tr[k] += val * log((f2)l);
        return;
    }
    int mid = (l+r) >> 1;
    if(mid < lmt) {
        val += sum[ls[k]]; ls[k] = 0;
        change1(rs[k],mid+1,r,lmt,val);
    }
    else change1(ls[k],l,mid,lmt,val);
    sum[k] = sum[ls[k]] + sum[rs[k]];
    tr[k] = tr[ls[k]] + tr[rs[k]];
}

void change2(int &k,int l,int r,int lmt,int val) {
    if(!k) k = ++sz;
    if(l==r) {
        sum[k] += val;
        tr[k] += lmt * log((f2)l);
        return;
    }
    int mid = (l+r) >> 1;
    if(mid +1 > lmt) {
        val += sum[rs[k]]; rs[k] = 0;
        change2(ls[k],l,mid,lmt,val);
    }
    else change2(rs[k],mid+1,r,lmt,val);
    sum[k] = sum[ls[k]] + sum[rs[k]];
    tr[k] = tr[ls[k]] + tr[rs[k]];
} 

inline int get(int k,int l,int r,int kth) {
    if(l==r) return l;
    int mid = (l+r) >> 1;
    if(sum[ls[k]] >= kth) return get(ls[k],l,mid,kth);
    else return get(rs[k],mid+1,r,kth-sum[ls[k]]);
}

int tt;

int main() {
    int x,y,opt;
    cin >> m;
    for(int i=1;i<=m;++i) {
        opt = read();
        if(opt == 1) {
            val[++cnt] = read();
            fa[cnt] = cnt, size[cnt] = 1;
            insert(root[cnt],1,Max,val[cnt],log((f2)val[cnt]));
        }
        else if(opt == 2) {
            x = read(), y = read();
            int fx = find(x), fy = find(y);
            if(fx == fy) continue;
            if(size[fx] < size[fy]) swap(fx,fy);
            merge(root[fx],root[fy],1,Max);
            fa[fy] = fx; size[fx] += size[fy];
        }
        else if(opt == 3) {
            x = read(), y = read();
            change1(root[find(x)], 1, Max, y, 0);
        }
        else if(opt == 4) {
            x = read(), y = read();
            change2(root[find(x)], 1, Max, y, 0);
        }
        else if(opt == 5) {
            x = read(), y = read();
            printf("%d\n",get(root[find(x)],1,Max,y));
        }
        else if(opt == 6) {
            x = read(), y = read();
            printf("%d\n",tr[root[find(x)]] > tr[root[find(y)]] ? 1 : 0);
        }
        else if(opt == 7) {
            x = read();
            printf("%d\n",size[find(x)]);
        }
        else if(opt == 8) x = read(), y = read();
        else x = read();
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP