求助一道站外题
  • 板块学术版
  • 楼主Ame__
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/8/28 19:06
  • 上次更新2023/11/5 14:05:22
查看原帖
求助一道站外题
245875
Ame__楼主2020/8/28 19:06

RT,BZOJ4399魔法少女LJJ,动态开点貌似写炸了不怎么会调,递归到一半就不继续开点了(求助dalao指点一下

#include<bits/stdc++.h>
    
#define LL long long
    
#define _ 0

using namespace std;
    
/*Grievous Lady*/
    
template <typename T> void read(T & t){
    t = 0;int f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f =- 1;ch = getchar();}
    do{t = t * 10 + ch - '0';ch = getchar();}while(ch >= '0' && ch <= '9');t *= f;
}
    
#define int long long

#define INF 1000000000

const int kato = 4e5 + 10;

int abi[kato] , tot;

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

struct tree{
    protected:

        #define mid ((l + r) >> 1)

        struct node{
            node *ch[2];
            LL sum; 
            double lg;
            node(LL sum = 0 , double lg = 0.0): sum(sum) , lg(lg){
                ch[0] = ch[1] = NULL;
            }
            inline void up(){
                sum = ch[0] -> sum + ch[1] -> sum;
                lg = ch[0] -> lg + ch[1] -> lg;
            }
        }*root[kato];

        inline void build(node *&o , int l , int r , int x , int val , double tmp){
            printf("%lld %lld %lld\n" , l , r , mid);
            if(!o) o = new node();
            if(l == r){ 
                o -> sum += val;
                o -> lg += (double)val * tmp;
                return;
            }
            // cout << "QAQ" << '\n';
            if(x <= mid) build(o -> ch[0] , l , mid , x , val , tmp);
            else build(o -> ch[1] , mid + 1 , r , x , val , tmp);
            o -> up();
        }

        inline void merge(node *&x , node *y){
            if(!x) return (void)(x = y);
            if(!y) return;
            x -> sum = (x -> sum + y -> sum) , x -> lg = (x -> lg + y -> lg);
            merge(x -> ch[0] , y -> ch[0]); merge(x -> ch[1] , y -> ch[1]);
        }

        inline int find_small(node *&o , int l , int r , int k){
            int res = 0;
            if(!o || l >= k) return 0;
            if(r < k) {
                res = o -> sum;
                o = NULL;
                return res;
            }
            if(l == r) return 0;
            res += find_small(o -> ch[0] , l , mid , k);
            res += find_small(o -> ch[1] , mid + 1 , r , k);
            o -> up();
            return res;
        }

        inline int find_big(node *&o , int l , int r , int k){
            int res = 0;
            if(!o || l >= k) return 0;
            if(l > k) {
                res = o -> sum;
                o = NULL;
                return res;
            }
            if(l == r) return 0;
            res += find_small(o -> ch[0] , l , mid , k);
            res += find_small(o -> ch[1] , mid + 1 , r , k);
            o -> up();
            return res;
        }

        inline int kth(node *o , int l , int r , int k){
            if(l == r){
                return l;
            }
            if(k <= o -> ch[0] -> sum){
                return kth(o -> ch[0] , l , mid , k - o -> ch[0] -> sum);
            }
            else return kth(o -> ch[1] , mid + 1 , r , k - o -> ch[0] -> sum);
        }

    public:

        inline void add(int cnt , int x , int val , double tmp){
            build(root[cnt] , 1 , INF , x , val , tmp);
        }

        inline void merge(int x , int y){
            merge(root[x] , root[y]);
        }

        inline int find_small(int x , int k){
            return find_small(root[x] , 1 , INF , k);
        }

        inline int find_big(int x , int k){
            return find_big(root[x] , 1 , INF , k);
        }

        inline int kth(int x , int k){
            return kth(root[x] , 1 , INF , k);
        }

        inline int judge(int x , int y){
            return root[x] -> lg > root[y] -> lg ? 1 : 0;
        }

        inline ask(int x){
            return root[x] -> sum;
        }

}yuni;

int m , opt , x , y;

inline int Ame_(){
    read(m);
    for(int i = 1;i <= kato;i ++) abi[i] = i;
    for(; m --> 0 ;){
        read(opt);
        if(opt == 1){ 
            read(x); yuni.add(++ tot , x , 1 , log(x)); 
        }
        if(opt == 2){ 
            read(x) , read(y); int fx = find(x) , fy = find(y); 
            if(fx != fy){ 
                abi[fy] = fx;
                yuni.merge(fx , fy);
            }
        }
        if(opt == 3){
            read(x) , read(y);
            int fx = find(x);
            int res = yuni.find_small(fx , y);
            yuni.add(fx , y , res , log(y));
        }
        if(opt == 4){
            read(x) , read(y);
            int fx = find(x);
            int res = yuni.find_big(fx , y);
            yuni.add(fx , y , res , log(y));
        }
        if(opt == 5){ 
            read(x) , read(y);
            int fx = find(x); 
            printf("%lld\n", yuni.kth(fx , y)); 
        }
		if(opt == 6){ 
            read(x) , read(y);
            int fx = find(x) , fy = find(y);
            printf("%lld\n", yuni.judge(fx , fy)); 
        }
		if(opt == 7){ 
            read(x);
            int fx = find(x);
            printf("%lld\n" , yuni.ask(fx)); 
        }
		if(opt == 8){ 
            read(x) , read(y); 
        }
		if(opt == 9){ read(x); }
    }
    return ~~(0^_^0);
}
    
int Ame__ = Ame_();
    
signed main(){;}

/*
12
1 2
1 3
1 4
1 5
1 6
2 1 2
2 2 3
2 3 4
2 4 5
9 1
3 2 5
5 3 4
*/
2020/8/28 19:06
加载中...