不会用typedef
by AlgoEmperor @ 2018-07-08 17:05:10
不是都用的数组吗，指针的话~~我猜~~是这么用
```
struct tree
{
int data;
tree *L,*R;
};
tree[MAXN];
exist: tree[i];//当前节点
Lchild: tree[i].L->data;//访问左孩子
Rchild: tree[i].R->data;//访问右孩子
```
by AlgoEmperor @ 2018-07-08 17:09:08
@[Ofnoname](/space/show?uid=73489) @[隔壁小邱](/space/show?uid=22539) 应该是tree->l->data
by moye到碗里来 @ 2018-07-08 17:27:12
我把我代码发出来吧。typedef与struct效果差不多的
by moye到碗里来 @ 2018-07-08 17:27:55
这个是finger_tree
```
#include<bits/stdc++.h>
#define MAXN 300006
using namespace std;
struct Node
{
int val,size;
Node *ls,*rs;
void pushup()
{
if(ls==NULL)return ;
size = ls->size + rs->size;
val = rs->val;
}
Node(int v,int s,Node *l,Node *r):val(v),size(s),ls(l),rs(r){}
Node(){}
}pool[MAXN];
int cnt = 0;
Node *root = NULL;
Node *NewNode(int val,int size,Node *ls,Node *rs)
{
pool[cnt] = Node(val,size,ls,rs);
return &pool[cnt++];
}
int find(int k,Node *rt)
{
if(rt->size == 1)return rt->val;
if(k<=rt->ls->size)return find(k,rt->ls);
else return find(k-rt->ls->size,rt->rs);
}
int Rank(int x,Node *rt)
{
if(rt->size == 1)
{
return 1;
}
else
{
if(x<=rt->ls->val){
return Rank(x,rt->ls);
}
else{
return Rank(x,rt->rs)+rt->ls->size;
}
}
}
inline void maintain(Node *rt)
{
if(rt->ls->size>rt->rs->size*4)
{
rt->rs = NewNode(rt->rs->val,rt->ls->rs->size+rt->rs->size,rt->ls->rs,rt->rs);
Node *tmp = rt->ls;rt->ls = rt->ls->ls;*tmp = *rt->rs;rt->rs = tmp;
cnt--;
}
else if(rt->ls->size*4<rt->rs->size)
{
rt->ls = NewNode(rt->rs->ls->val,rt->rs->ls->size+rt->ls->size,rt->ls,rt->rs->ls);
Node *tmp = rt->rs;rt->rs = rt->rs->rs;*tmp = *rt->ls;rt->ls = tmp;
cnt--;
}
}
void ins(int val,Node *&rt)
{
if(rt == NULL){rt = NewNode(val,1,NULL,NULL);return ;}
if(rt->size == 1)
{
rt->ls = NewNode(min(val,rt->val),1,NULL,NULL);
rt->rs = NewNode(max(val,rt->val),1,NULL,NULL);
}
else
{
if(val>rt->ls->val)ins(val,rt->rs);
else ins(val,rt->ls);
}
rt->pushup();
maintain(rt);
}
void del(Node *rt,Node *fa,int val)
{
if(rt->size == 1)
*fa = fa->ls->val == val?*fa->rs:*fa->ls;
else
{
if(val<=rt->ls->val)del(rt->ls,rt,val);
else del(rt->rs,rt,val);
}
rt->pushup();
}
int main()
{
int n;
scanf("%d",&n);
root = NewNode(2147483647,1,NULL,NULL);
for(int i = 1; i <= n; i++)
{
int opt,x;
scanf("%d %d",&opt,&x);
if(opt == 1)ins(x,root);
if(opt == 2)del(root,NULL,x);
if(opt == 3)printf("%d\n",Rank(x,root));
if(opt == 4)printf("%d\n",find(x,root));
if(opt == 5)printf("%d\n",find(Rank(x,root)-1,root));
if(opt == 6)printf("%d\n",find(Rank(x+1,root),root));
}
}
```
by moye到碗里来 @ 2018-07-08 17:28:55
谢谢！~~可能我这一辈子都用不上~~
by AlgoEmperor @ 2018-07-08 17:31:50
找不到平衡树了放个线段树的。。。。
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
struct data{
int x,y,h,f;
bool operator < (const data p) const {
if(h == p.h)return f < p.f;
return h < p.h;
}
}l[5005*2];
ll ans = 0;
inline ll abs(int a,int b){return a > b ? a - b : b - a;}
struct node{
int l,r,len,num,lazy;
node *ls,*rs;
node(int a,int b,int c,int d,node *e,node *f,int l):l(a),r(b),len(c),num(d),ls(e),rs(f),lazy(l){}
node(){}
inline void pushup(){
if(lazy)return ;
len = ls->len + rs->len;
l = ls->l;r = rs->r;
num = ls->num + rs->num;
if(ls->r && rs->l)num--;
}
}pool[20005*2];
node *NewNode(int l,int r,int len,int num,node *ls,node *rs,int lazy){
static int cnt = 0;
pool[cnt] = node(l,r,len,num,ls,rs,lazy);
return &pool[cnt++];
}
node *root;
node *build(int l,int r){
node *rt = NewNode(0,0,0,0,NULL,NULL,0);int mid = (l + r) >> 1;
if(l < r){
rt->ls = build(l,mid);
rt->rs = build(mid+1,r);
}
return rt;
}
void add(node *rt,int l,int r,int L,int R){
if(L <= l && r <= R){
if(!rt->lazy){
rt->l = rt->r = 1;
rt->len = r - l + 1;
rt->num = 1;
}
rt->lazy += 1;return ;
}
int mid = (l + r) >> 1;
if(mid >= L)add(rt->ls,l,mid,L,R);
if(mid < R)add(rt->rs,mid+1,r,L,R);
rt->pushup();
}
void del(node *rt,int l,int r,int L,int R){
if(L <= l && r <= R){
rt->lazy--;
if(!rt->lazy){
if(l == r){
rt->num = rt->len = rt->l = rt->r = 0;
}
else rt->pushup();
}
return ;
}
int mid = (l + r) >> 1;
if(mid >= L)del(rt->ls,l,mid,L,R);
if(mid < R)del(rt->rs,mid+1,r,L,R);
rt->pushup();
}
int cnt2 = 0;
int main()
{
scanf("%lld",&n);
for(int i = 1; i <= n; i++){
int x,y,x1,y1;
scanf("%d %d %d %d",&x,&y,&x1,&y1);
l[++cnt2].x = x + 10000 + 1;l[cnt2].y = x1 + 10000 + 1;l[cnt2].h = y;l[cnt2].f = 0;
l[++cnt2].x = x + 10000 + 1;l[cnt2].y = x1 + 10000 + 1;l[cnt2].h = y1;l[cnt2].f = 1;
}
sort(l + 1,l + 1 + cnt2);
root = build(1,20005);
int prelines=0,prelength=0;
l[0].h = l[1].h;
for(int i = 1; i <= cnt2; i++){
if(l[i].f == 0)add(root,1,20005,l[i].x,l[i].y-1);
else del(root,1,20005,l[i].x,l[i].y-1);
ans += prelines * 2 * (l[i].h - l[i-1].h);
// if(root->num != prelines && (l[i].y - l[i].x + 1) == abs(prelength,root->len))ans--;
prelines = root->num;
ans += abs(root->len,prelength);
prelength = root->len;
}
printf("%lld",ans);
}
矩形周长。。
```
by moye到碗里来 @ 2018-07-08 17:36:44
@[Ofnoname](/space/show?uid=73489) 不不不,这种方法是不用数组的,是直接从根节点访问,根节点的左右指针也是结构体类型
by SkyLiYu @ 2018-07-08 17:40:01
C++的Class了解一下：~~与struct并无太大区别~~
```cpp
#include<bits/stdc++.h>
class Tree
{
public:
char data;
Tree *son[2];
}root,*now;
int main()
{
root.son[0]=new Tree;//新增一个结点
root.son[0]->data='?';//变量名后用小数点，指针后用箭头："->"
root.son[0]->son[0]=new Tree;//皮一下
now=&root;//取地址
printf("%c",now->son[0]->data);//见输出
return 0;
}
```
Output:
```cpp
?
```
by 吹雪吹雪吹 @ 2018-07-08 17:40:32
@[假装老船长](/space/show?uid=32831) 您这种方法怎么判断一个节点是不是空节点,求指教,谢谢
by SkyLiYu @ 2018-07-08 17:45:00