treap | kugwzk's space

题意就是题目上说的那样。。。给出一个n个数的序列，对于这个序列询问区间长度\(>=L\)且满足区间和\(>=M\)的区间的个数。数组下标从\(1\)开始，\(N\leq 10000,-100000\leq M,a[i] \leq 100000\)。

很久之前和ClearY吃饭的时候讨论的，后来她居然弄到校赛里面去了。。。

维护出来一个前缀和，那么对于位置\(pos\)来说，对答案的贡献就是位置\(i\)满足\(i <= pos-L\)，而且\(sum[pos]-sum[i] >= M\)。那么我们从前往后扫，维护一棵平衡树，对于每个位置\(i\)找到他往后的\(L\)个位置\(pos\)，查询比\(a[pos]-M\)小于等于的数有多少个就好了。这个treap写个rank函数就好了。

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define oo ~0u>>1
#define maxn 10010
#define REP(i,x,y) for(int i=x;i<(y);i++)
using namespace std;
typedef long long ll;
int n,m,L,sum[maxn];
struct node* null;
struct node{
    int key,s,w,num;
    node* ch[2];
    node(int _key):key(_key),s(1),w(rand()),num(1){ch[0]=ch[1]=null;}
    inline void pushup(){s=ch[0]->s+ch[1]->s+num;}
}*root;
inline void rot(node* &rt,const bool& d){       //d=o left d=1 right
    node* k=rt->ch[d^1];
    rt->ch[d^1]=k->ch[d];
    k->ch[d]=rt;
    rt->pushup();k->pushup();
    rt=k;
}
inline void Insert(node* &rt,const int& key){
    if(rt==null) {
        rt=new node(key);return ;
    }
    bool d=key > rt->key;
    if(key==rt->key){
        rt->num++;
        rt->pushup();
        return ;
    }
    else Insert(rt->ch[d],key);
    if(rt->ch[d]->w < rt->w) rot(rt,d^1);
    else rt->pushup();
}
inline int Rank(node* &rt,const int& key){
    if(rt==null) return 0;           //非法情况
    int ls=rt->ch[0]->s;
    if(key<rt->key) return Rank(rt->ch[0],key);
    else return ls+rt->num+Rank(rt->ch[1],key);
}
inline void init(){
    null=new node(0);null->ch[0]=null->ch[1]=null;null->s=0;null->w=oo;null->num=0;
    root=null;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        init();
        scanf("%d %d %d",&n,&L,&m);
        REP(i,1,n+1) {
            int tmp;scanf("%d",&tmp);
            sum[i]=sum[i-1]+tmp;
        }
        int ans=0;
        for(int i=0;i+L<=n;i++){
            Insert(root,sum[i]);
            int pos=i+L;
            int tmp=Rank(root,sum[pos]-m);
            ans+=tmp;
        }
        printf("%d\n",ans);
    }
}

#include <cstdio>

#include <ctime>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <string>

#include <set>

#include <stack>

#include <map>

#include <cmath>

#include <vector>

#include <iostream>

#include <algorithm>

#define inf 0x3f3f3f3f

#define oo ~0u>>1

#define maxn 10010

#define REP(i,x,y) for(int i=x;i<(y);i++)

using namespace std;

typedef long long ll;

int n,m,L,sum[maxn];

struct node* null;

struct node{

int key,s,w,num;

node* ch[2];

node(int _key):key(_key),s(1),w(rand()),num(1){ch[0]=ch[1]=null;}

inline void pushup(){s=ch[0]->s+ch[1]->s+num;}

}*root;

inline void rot(node* &rt,const bool& d){ //d=o left d=1 right

node* k=rt->ch[d^1];

rt->ch[d^1]=k->ch[d];

k->ch[d]=rt;

rt->pushup();k->pushup();

rt=k;

}

inline void Insert(node* &rt,const int& key){

if(rt==null) {

rt=new node(key);return ;

}

bool d=key > rt->key;

if(key==rt->key){

rt->num++;

rt->pushup();

return ;

}

else Insert(rt->ch[d],key);

if(rt->ch[d]->w < rt->w) rot(rt,d^1);

else rt->pushup();

}

inline int Rank(node* &rt,const int& key){

if(rt==null) return 0; //非法情况

int ls=rt->ch[0]->s;

if(key<rt->key) return Rank(rt->ch[0],key);

else return ls+rt->num+Rank(rt->ch[1],key);

}

inline void init(){

null=new node(0);null->ch[0]=null->ch[1]=null;null->s=0;null->w=oo;null->num=0;

root=null;

}

int main()

{

int T;scanf("%d",&T);

while(T--){

init();

scanf("%d %d %d",&n,&L,&m);

REP(i,1,n+1) {

int tmp;scanf("%d",&tmp);

sum[i]=sum[i-1]+tmp;

}

int ans=0;

for(int i=0;i+L<=n;i++){

Insert(root,sum[i]);

int pos=i+L;

int tmp=Rank(root,sum[pos]-m);

ans+=tmp;

}

printf("%d\n",ans);

}

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：

1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi – xil+IYi – Yil≤C.

2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

Input

第1行输入N和C，之后N行每行输入一只奶牛的坐标．

Output

仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开．

Sample Input

4 2
1 1
3 3
2 2
10 10

* Line 1: A single line with a two space-separated integers: the
number of cow neighborhoods and the size of the largest cow
neighborhood.

Sample Output

2 3

OUTPUT DETAILS:
There are 2 neighborhoods, one formed by the first three cows and
the other being the last cow. The largest neighborhood therefore
has size 3.

维护连通块有个直观的想法就是用并查集，但是O(n^2)连边的话肯定爆炸。想到BZOJ 4152这个题目通过点只连和自己距离最近的点把连边复杂度降为O(n)，类似我们只需要找到某个点和它曼哈顿距离最近的两个点相连即可。但是。。。并不知道该怎么找。。。

查了一下，发现了一个曼哈顿距离转换为切比雪夫距离的方法：设一个点为A(x,y)，把他的坐标变换为A'(x+y,x-y)。这时候原来两点间的曼哈顿距离就恰恰转换为了新坐标系下两点的切比雪夫距离即：max(|x1-x2|,|y1-y2|)。

这样的好处在于我们可以把x,y这两维拆开考虑了。由于我们已经按照切比雪夫距离来计算了，那么先把所有点按照x升序排序。然后维护一个队列，这个队列里的元素x坐标之差不超过C，类似于滑动窗口的处理。至于y坐标，我们考虑把队列里的所有点的y坐标加入到一棵平衡树内，这样的话我们可以在logN的时间内查出前驱和后继，再进行判断前驱和后继的y坐标和该点的距离是否在C的范围内。只需要连前驱和后继即可。这个就可以用并查集来做了。

所以，我写了棵双关键词的treap和并查集，太久没写过treap了，调了好久的bug。。。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf 0x3f3f3f3f
#define oo ~0u>>1
#define maxn 100005
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template <class T>
inline void read(T &res){
    char c;res=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9'){
        res=res*10+(c-'0');
        c=getchar();
    }
}
/////////
int n,c,que[maxn],cnt[maxn];
pii pp[maxn];
int par[maxn],ran[maxn];

/***treap***/
struct node* null;
struct node{
    int key,id,s,w;
    node* ch[2];
    node(int _key,int _id):key(_key),id(_id),s(1),w(rand()){ch[0]=ch[1]=null;}
    inline void pushup(){s=ch[0]->s+ch[1]->s+1;}
}*root;
inline void rot(node* &rt,const bool& d){       //d=o left d=1 right
    node* k=rt->ch[d^1];
    rt->ch[d^1]=k->ch[d];
    k->ch[d]=rt;
    rt->pushup();k->pushup();
    rt=k;
}
inline void Insert(node* &rt,const int& key,const int& id){
    if(rt==null) {
        rt=new node(key,id);return ;
    }
    bool d=key > rt->key ;
    if(key==rt->key&&id>rt->id) d= id < rt->id;
    Insert(rt->ch[d],key,id);
    if(rt->ch[d]->w < rt->w)        //小根堆
        rot(rt,d^1);
    else rt->pushup();
}
inline void Remove (node* &rt,const int& key,const int& id){
    if(rt==null) return ;
    int d=key > rt->key;
    if(key==rt->key){
        if(id==rt->id){
            d=rt->ch[0]->w > rt->ch[1]->w ;
            if(rt->ch[d]==null){
                delete rt;
                rt=null;
                return ;
            }
            rot(rt,d^1);
            Remove(rt->ch[d^1],key,id);
        }
        else Remove(rt->ch[id < rt->id],key,id);
    }
    else Remove(rt->ch[d],key,id);
    rt->pushup();
}
inline int suc(const int& k){
    node* rt=root;
    int res=-1,tmp=-1;
    while(rt!=null){
        if(rt->key>k){
            res=rt->key;tmp=rt->id;
            rt=rt->ch[0];
        }
        else rt=rt->ch[1];
    }
    return tmp;
}
inline int pre(const int& k){
    node* rt=root;
    int res=-1,tmp=-1;
    while(rt!=null){
        if(rt->key<=k){
            res=rt->key;tmp=rt->id;
            rt=rt->ch[1];
        }
        else rt=rt->ch[0];
    }
    return tmp;
}
inline void init(){
    null=new node(0,-1);null->ch[0]=null->ch[1]=null;null->s=0;null->w=oo;
    root=null;
    for(int i=0;i<maxn;i++) {par[i]=i;ran[i]=0;}
}
void print(node* &rt)
{
    if (rt == null) return ;
    print(rt->ch[0]);
    printf("%d %d\n", rt->key,rt->id,rt->w);
    printf("%d %d\n",rt->ch[0]->w==oo,rt->ch[1]->w==oo);
    print(rt->ch[1]);
}
//////////
/***DSU***/
inline int fin(int x){
    while(x!=par[x])
        x=par[x]=par[par[x]];
    return x;
}
inline void unite(int x,int y){
    int fa1=fin(x);
    int fa2=fin(y);
    if(fa1==fa2) return ;
    if(ran[fa1]>ran[fa2]){
        par[fa2]=par[fa1];
        ran[fa1]+=ran[fa2];
    }
    else{
        par[fa1]=par[fa2];
        ran[fa2]+=ran[fa1];
    }
}
////////
int main()
{
    init();
    read(n);read(c);
    for(int i=1;i<=n;i++){
        read(pp[i].first);read(pp[i].second);
        int xx=pp[i].first;pp[i].first=pp[i].first+pp[i].second;
        pp[i].second=xx-pp[i].second;
    }
    sort(pp+1,pp+1+n);
    int h=1,t=1;
    for(int i=1;i<=n;i++){
        while(h<t&&pp[i].first-pp[que[h]].first>c){
            Remove(root,pp[que[h]].second,que[h]);
            h++;
        }
        int pos=suc(pp[i].second);
        if(pos!=-1&&pp[que[pos]].second-pp[i].second<=c) {
            int fa1=fin(i);int fa2=fin(pos);
            unite(fa1,fa2);
        }
        pos=pre(pp[i].second);
        if(pos!=-1&&pp[i].second-pp[que[pos]].second<=c){
            int fa1=fin(i);int fa2=fin(pos);
            unite(fa1,fa2);
        }
        Insert(root,pp[i].second,i);
        que[t]=i;t++;
        //print(root);
    }
    int num=0,maxx=0;
    for(int i=1;i<=n;i++){
        if(fin(i)==i)
            num++;
        cnt[fin(i)]++;
        maxx=max(maxx,cnt[fin(i)]);
    }
    printf("%d %d\n",num,maxx);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <queue>

#define inf 0x3f3f3f3f

#define oo ~0u>>1

#define maxn 100005

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

template <class T>

inline void read(T &res){

char c;res=0;

while((c=getchar())<'0'||c>'9');

while(c>='0'&&c<='9'){

res=res*10+(c-'0');

c=getchar();

}

/////////

int n,c,que[maxn],cnt[maxn];

pii pp[maxn];

int par[maxn],ran[maxn];

/***treap***/

struct node* null;

struct node{

int key,id,s,w;

node* ch[2];

node(int _key,int _id):key(_key),id(_id),s(1),w(rand()){ch[0]=ch[1]=null;}

inline void pushup(){s=ch[0]->s+ch[1]->s+1;}

}*root;

inline void rot(node* &rt,const bool& d){ //d=o left d=1 right

node* k=rt->ch[d^1];

rt->ch[d^1]=k->ch[d];

k->ch[d]=rt;

rt->pushup();k->pushup();

rt=k;

}

inline void Insert(node* &rt,const int& key,const int& id){

if(rt==null) {

rt=new node(key,id);return ;

}

bool d=key > rt->key ;

if(key==rt->key&&id>rt->id) d= id < rt->id;

Insert(rt->ch[d],key,id);

if(rt->ch[d]->w < rt->w) //小根堆

rot(rt,d^1);

else rt->pushup();

}

inline void Remove (node* &rt,const int& key,const int& id){

if(rt==null) return ;

int d=key > rt->key;

if(key==rt->key){

if(id==rt->id){

d=rt->ch[0]->w > rt->ch[1]->w ;

if(rt->ch[d]==null){

delete rt;

rt=null;

return ;

}

rot(rt,d^1);

Remove(rt->ch[d^1],key,id);

}

else Remove(rt->ch[id < rt->id],key,id);

}

else Remove(rt->ch[d],key,id);

rt->pushup();

}

inline int suc(const int& k){

node* rt=root;

int res=-1,tmp=-1;

while(rt!=null){

if(rt->key>k){

res=rt->key;tmp=rt->id;

rt=rt->ch[0];

}

else rt=rt->ch[1];

}

return tmp;

}

inline int pre(const int& k){

node* rt=root;

int res=-1,tmp=-1;

while(rt!=null){

if(rt->key<=k){

res=rt->key;tmp=rt->id;

rt=rt->ch[1];

}

else rt=rt->ch[0];

}

return tmp;

}

inline void init(){

null=new node(0,-1);null->ch[0]=null->ch[1]=null;null->s=0;null->w=oo;

root=null;

for(int i=0;i<maxn;i++) {par[i]=i;ran[i]=0;}

}

void print(node* &rt)

{

if (rt == null) return ;

print(rt->ch[0]);

printf("%d %d\n", rt->key,rt->id,rt->w);

printf("%d %d\n",rt->ch[0]->w==oo,rt->ch[1]->w==oo);

print(rt->ch[1]);

}

//////////

/***DSU***/

inline int fin(int x){

while(x!=par[x])

x=par[x]=par[par[x]];

return x;

}

inline void unite(int x,int y){

int fa1=fin(x);

int fa2=fin(y);

if(fa1==fa2) return ;

if(ran[fa1]>ran[fa2]){

par[fa2]=par[fa1];

ran[fa1]+=ran[fa2];

}

else{

par[fa1]=par[fa2];

ran[fa2]+=ran[fa1];

}

////////

int main()

{

init();

read(n);read(c);

for(int i=1;i<=n;i++){

read(pp[i].first);read(pp[i].second);

int xx=pp[i].first;pp[i].first=pp[i].first+pp[i].second;

pp[i].second=xx-pp[i].second;

}

sort(pp+1,pp+1+n);

int h=1,t=1;

for(int i=1;i<=n;i++){

while(h<t&&pp[i].first-pp[que[h]].first>c){

Remove(root,pp[que[h]].second,que[h]);

h++;

}

int pos=suc(pp[i].second);

if(pos!=-1&&pp[que[pos]].second-pp[i].second<=c) {

int fa1=fin(i);int fa2=fin(pos);

unite(fa1,fa2);

}

pos=pre(pp[i].second);

if(pos!=-1&&pp[i].second-pp[que[pos]].second<=c){

int fa1=fin(i);int fa2=fin(pos);

unite(fa1,fa2);

}

Insert(root,pp[i].second,i);

que[t]=i;t++;

//print(root);

}

int num=0,maxx=0;

for(int i=1;i<=n;i++){

if(fin(i)==i)

num++;

cnt[fin(i)]++;

maxx=max(maxx,cnt[fin(i)]);

}

printf("%d %d\n",num,maxx);

}

kugwzk's space

曾经的acmer

标签归档：treap

HPU 1193: Interval（查询区间长度大于特定值且区间和大于特定值的区间个数）

BZOJ 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居（treap+并查集）

Description

Input

Output

Sample Input

Sample Output

BZOJ上的USACO 第一弹