@[chen_zhe](/space/show?uid=8457)
by 密期望 @ 2018-10-10 19:56:54
你家爆空间不改程序改题目…………？
by yyy2015c01 @ 2018-10-10 19:57:17
@[yyy2015c01](/space/show?uid=5846) 我再自己改改吧，打扰了
by 密期望 @ 2018-10-10 20:02:11
@[密期望](/space/show?uid=81705) 用bitset试试？
by xiaolou @ 2018-10-10 20:02:57
除了指针的空间我真的不知道怎么优化了，难道64位下真的不能用指针？
```
#include<cstdio>
typedef long long ll;
const int N=1e5+10;
template < typename data_type >
data_type mid(data_type a,data_type b){
return a+((b-a)>>1);
}
int lowbit(int x){
return x&-x;
}
char mem[N*5000];//只开不用的话不算空间
int mem_p;
/*
整个节点20字节，如果不用指针则为12字节，节省近一半空间
*/
class segment_tree{
private:
int data;
segment_tree *son[2];
void check_0(){
if(son[0]==this){
son[0]=new segment_tree();
}
}
void check_1(){
if(son[1]==this){
son[1]=new segment_tree();
}
}
public:
void *operator new(size_t size){
mem_p+=size;
return mem+mem_p-size;
}
segment_tree():data(0){
son[0]=son[1]=this;
}
void update(int begin,int end,int pos,int data_){
data+=data_;
int mm=mid(begin,end);
if(begin!=end){
if(pos<=mm){
check_0();
son[0]->update(begin,mm,pos,data_);
}else{
check_1();
son[1]->update(mm+1,end,pos,data_);
}
}
}
int get(int begin,int end,int begin_,int end_){
int mm=mid(begin,end);
if(!data){
return 0;
}
if(begin==begin_&&end==end_){
return data;
}
if(end_<=mm){
return son[0]==this?0:son[0]->get(begin,mm,begin_,end_);
}
if(begin_>mm){
return son[1]==this?0:son[1]->get(mm+1,end,begin_,end_);
}
return (son[0]==this?0:son[0]->get(begin,mm,begin_,mm))+(son[1]==this?0:son[1]->get(mm+1,end,mm+1,end_));
}
};
int n,m;
segment_tree *s[N];
void update(int pos_out,int pos_in,int data_){
while(pos_out<=n){
s[pos_out]->update(1,n,pos_in,data_);
pos_out+=lowbit(pos_out);
}
}
int get(int begin_out,int end_out,int begin_in,int end_in){
int ret=0;
while(end_out){
ret+=s[end_out]->get(1,n,begin_in,end_in);
end_out-=lowbit(end_out);
}
begin_out--;
while(begin_out){
ret-=s[begin_out]->get(1,n,begin_in,end_in);
begin_out-=lowbit(begin_out);
}
return ret;
}
int pos[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
s[i]=new segment_tree();
}
int p;
ll count=0;
for(int i=1;i<=n;i++){
scanf("%d",&p);
pos[p]=i;
if(p!=n&&i!=1){
count+=get(1,i-1,p+1,n);
}
update(i,p,1);
}
for(int i=0;i<m;i++){
printf("%lld\n",count);
scanf("%d",&p);
if(p!=n&&pos[p]!=1){
count-=get(1,pos[p]-1,p+1,n);
}
if(p!=1&&pos[p]!=n){
count-=get(pos[p]+1,n,1,p-1);
}
update(pos[p],p,-1);
}
return 0;
}
```
那么问题来了，CCF是多少位的？
by 密期望 @ 2018-10-10 20:21:35
@[密期望](/space/show?uid=81705)
我也被卡空间了T T
难道只能用cdq过吗....
树状数组套权值线段树的空间复杂度真的不优越啊.....
by misinclair @ 2018-10-11 08:45:16
乖乖换数组吧，我的指针也被卡了
by 地狱小鬼366 @ 2018-12-04 13:11:23