MinamiMelon
0%

珂朵莉树-Chtholly-Tree-学习记录

发表于

用作处理随机数据，具有区间赋值操作的序列操作问题 把值相同的区间合并成一个结点保存在 set 里面。 对于add，assign 和 sum 操作，用 set 实现的珂朵莉树的复杂度为\(O(nloglogn)\)，而用链表实现的复杂度为\(O(nlog)\)。 

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
typedef long long ll;
struct Node{
  ll l, r;//闭区间！
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(ll x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l, ll r, ll v){//区间赋值，作为时间复杂度保证
	auto itr=split(r+1),itl=split(l);//进行求取区间左右端点操作时，必须先 split 右端点，再 split 左端点。若先 split 左端点，返回的迭代器可能在 split 右端点的时候失效，可能会导致 RE。
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
//其他的操作，每块都操作（暴力）
void do_sth(ll l,ll r,ll v){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		//do something
	}
}
//例如，区间加
void add(ll l,ll r,ll v){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		itl->v+=v;	
	}
}
//例如，区间第k小的是几
ll kth(ll l,ll r,ll k){
	vector<pair<ll,ll> > v;
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		v.push_back(make_pair(itl->v,itl->r-itl->l+1));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();++i){
		k-=v[i].second;
		if(k<=0) return v[i].first;
	}
}
int main(){
	for(ll i=1;i<=n;++i){//区间初始化
        ll x;scanf("%lld",&x);
		odt.insert(Node(i,i,x));
	}
	return 0;
}
Willem, Chtholly and Seniorious

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
struct Node{
  ll l, r;
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(ll x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l, ll r, ll v){//区间赋值 
	auto itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
void add(ll l,ll r,ll v){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		itl->v+=v;	
	}
}
ll seed;
ll kth(ll l,ll r,ll k){
	vector<pair<ll,ll> > v;
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		v.push_back(make_pair(itl->v,itl->r-itl->l+1));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();++i){
		k-=v[i].second;
		if(k<=0) return v[i].first;
	}
}
int rnd(){
	int ret(seed);
	seed=(seed * 7 + 13)%1000000007;
    return ret;
}
ll qpow(ll a,ll p,ll mod){
    ll ans=1;
	a%=mod;
    while(p){
        if(p&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        p>>=1;
    }
    return ans%mod;
}
ll ask(ll l,ll r,ll x,ll y){
	auto itr=split(r+1),itl=split(l);
	ll ret=0;
	for(;itl!=itr;++itl) {
		ret=(ret+(itl->r-itl->l+1)*qpow(itl->v,x,y))%y;
	}
	return ret;
}
int main(){
	ll m,vmax;
	scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
	for(ll i=1;i<=n;++i){
		ll r=rnd();
		odt.insert(Node(i,i,(r%vmax)+1));
	}
	for(ll i=1;i<=m;++i){
		ll op=(rnd()%4)+1;
		ll l=rnd()%n+1;
		ll r=rnd()%n+1;
		if(l>r) swap(l,r);
		ll x;
		if(op==3){x=rnd()%(r-l+1)+1;}else{x=(rnd()%vmax)+1;}
		if(op==1){
			add(l,r,x);
		}else if(op==2){
			assign(l,r,x);
		}else if(op==3){
			printf("%lld\n",kth(l,r,x));
		}else if(op==4){
			ll y=rnd()%vmax+1;
			printf("%lld\n",ask(l,r,x,y));
		}
	}
	return 0;
}

BZOJ1858

0 l r 把 [l, r]区间内的所有数全变成 0

1 l r 把 [l, r] 区间内的所有数全变成 1

2 l r 把 [l,r] 区间内的所有数全部取反，也就是说把所有的 0 变成 1，把所有的 1 变成 0

3 l r 询问 [l, r] 区间内总共有多少个 1

4 l r 询问 [l, r] 区间内最多有多少个连续的 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
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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct Node{
  ll l, r;//闭区间！
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(ll x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l, ll r, ll v){//区间赋值 
	auto itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
void flipv(ll l,ll r){
    auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		itl->v^=1;
	}
}
ll ask1(ll l,ll r){
    auto itr=split(r+1),itl=split(l);
    ll ret=0;
	for(;itl!=itr;++itl) {
		if(itl->v==1){
            ret+=itl->r-itl->l+1;
        }
	}
    return ret;
}
ll ask2(ll l,ll r){
    auto itr=split(r+1),itl=split(l);
    ll ret=0,pre=0;
	for(;itl!=itr;++itl) {
		if(itl->v==1){
            ret=max(ret,pre=pre+itl->r-itl->l+1);
        }else{
            pre=0;
        }
	}
    return ret;
}
void getint(int &x){
    char c;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0';
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    int pos=1,val;
    getint(val);
	for(int i=2;i<=n;++i){//区间初始化
        ll x;getint(x);
        if(x!=val){
		    odt.insert(Node(pos,i-1,val));
            pos=i;
            val=x;
        }
	}
    odt.insert(Node(pos,n,val));
    while(m--){
        ll op,l,r;
        getint(op);getint(l);getint(r);
        ++l,++r;
        if(op<=1){
            assign(l,r,op);
        }else if(op==2){
            flipv(l,r);
        }else if(op==3){
            printf("%d\n",ask1(l,r));
        }else if(op==4){
            printf("%d\n",ask2(l,r));
        }
    }
	return 0;
}

luogu P4979

assign 操作需要优化才能通过 

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
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;

typedef int ll;
struct Node{
  ll l, r;
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(const ll &x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l,ll r,const ll &v){//区间赋值 
    set<Node>::iterator itr;
    if(r==n){
        itr=odt.end();
    }else{
        itr=--odt.upper_bound((Node){r+1, 0, 0});
        if(itr->v==v){
            r=itr->r;
        }else{
            if(itr->l!=r+1){
                ll tl=itr->l,tr=itr->r,tv=itr->v;
                odt.erase(itr);
                odt.insert(Node(tl,r,tv));
                itr=odt.insert(Node(r+1,tr,tv)).first;
            }
        }
    }
    auto itl=--odt.upper_bound((Node){l, 0, 0});
    if(itl->v==v){
        l=itl->l;
    }else{
        if(itl->l!=l){
            ll tl=itl->l,tr=itl->r,tv=itl->v;
            odt.erase(itl);
            odt.insert(Node(tl,l-1,tv));
            itl=odt.insert(Node(l,tr,tv)).first;
        }
    }
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
bool ask(const ll &l,const ll &r){
    auto itr=split(r+1);
    auto itl=split(l);
    int vn=itl->v,vp=-1;
    if(itl!=odt.begin()){
        auto it=itl;
        --it;
        vp=it->v;
    }
    ++itl;
    for(;itl!=itr;++itl){
        if(itl->v!=vn){
            return 0;
        }
    }
    if(itl!=odt.end()){
        if(itl->v==vp){
            return 0;
        }
    }
    return 1;
}
void getint(int &x){
    char c;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0';
}
inline char recd(char &o) {
    while ((o = getchar()) < 'A' || o > 'Z'); return o;
}
const int N=500000+5;
char s[N];
int main(){
    getint(n);
    int pos=1;
    char val=getchar();
    while(val<'A'||val>'C')
        val=getchar();
    for(int i=2;i<=n;++i){
        char c=getchar();
        if(c!=val){
            odt.insert(Node(pos,i-1,val-'A'));
            pos=i;
            val=c;
        }
    }
    odt.insert(Node(pos,n,val-'A'));
    int m,l,r;
    char op;
    getint(m);
    while(m--){
        recd(op);
        getint(l);getint(r);
        if(op=='A'){
            recd(op);
            assign(l,r,op-'A');
        }else{
            puts(ask(l,r)?"Yes":"No");
        }
    }
	return 0;
}