制作不易,点个赞呗
前置芝士:加法交换律
这几天在学加法交换律,然后老师出了道难题—A+BProblem,鄙人冥思苦想,想了三天三夜,终于想到一个加法交换律的解法。
众所周知,A+B=B+A,于是我们把两个数的位置换一下,他们和不变。交换位置自然而然就想到反转,什么数据结构干反转最熟练,当然是文艺平衡树了啊,于是我们可以先交换一下A,B,然后再求和,这个做法是不是很妙啊。
附上代码:
#include<bits/stdc++.h>
using namespace std;
inline int read(){
register int w=0,x=0;char ch;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return w?-x:x;
}
int n,m;
int a[100005];
struct fhq_treap{
int l,r;
int dat,size;
int val;
int tag;
}t[100005];
int root,tot;
inline int New(int k){
t[++tot].val=k;
t[tot].dat=rand();
t[tot].tag=0;
t[tot].size=1;
return tot;
}
inline void pushup(int p){
t[p].size=t[t[p].l].size+t[t[p].r].size+1;
}
inline void spread(int p){
if(t[p].tag){
swap(t[p].l,t[p].r);
t[t[p].l].tag^=1;
t[t[p].r].tag^=1;
t[p].tag=0;
}
}
inline void split(int p,int siz,int &x,int &y){
if(!p){
x=y=0;
return ;
}
spread(p);
if(t[t[p].l].size<siz){
x=p;
split(t[p].r,siz-t[t[p].l].size-1,t[p].r,y);
}
else{
y=p;
split(t[p].l,siz,x,t[p].l);
}
pushup(p);
}
inline int merge(int x,int y){
if(!x||!y) return x+y;
if(t[x].dat<t[y].dat){
spread(x);
t[x].r=merge(t[x].r,y);
pushup(x);
return x;
}
else {
spread(y);
t[y].l=merge(x,t[y].l);
pushup(y);
return y;
}
}
int x,y,z;
inline void insert(int k){
root=merge(root,New(k));
}
inline void reserve(int l,int r){
split(root,l-1,x,y);
split(y,r-l+1,y,z);
t[y].tag^=1;
root=merge(merge(x,y),z);
}
int sum=0;
inline void in_order(int p){
if(!p) return ;
spread(p);
in_order(t[p].l);
sum+=t[p].val;
in_order(t[p].r);
}
int g,h;
int main(){
n=read(),m=read();
insert(n),insert(m);
reserve(1,2);
in_order(root);
cout<<sum;
return 0;
}