牛客第一场
\(H.Matches\)
赛后卡过了非正解，记一下优化过程，感觉还是挺有用
- 缩短线段树长度。区间信息只记在左端点处，右端点只用于查询，因此在离散化的时候就去掉右端点，线段树只开左端点个数的长度。不影响查询时的范围。
- 线段树函数用记录左右端点代替传参。据说不同的机器在这里有差异，这题用传参的写法会卡不过去。
- 快读，去除冗余代码
H.Matches（线段树解）
#include
#define ll long long
using namespace std;
const int N = 1e6 + 9;
int n,a[N],b[N],cnt,d[N<<1],sum;
ll tmp,ans;
struct node{
int l,r,tag,L,R;
}c[N<<1];
struct tree{
int l,r;
ll siz,num;
}t[2][N<<2];
bool cmp(node x,node y){
return x.R'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void change(int p,int pos,ll L,ll R,int tag){
if(t[tag][p].l==t[tag][p].r){
t[tag][p].siz=max(t[tag][p].siz,R-L);
t[tag][p].num=max(t[tag][p].num,R);
return;
}
if(pos<=t[tag][p<<1].r)change(p<<1,pos,L,R,tag);
else change(p<<1|1,pos,L,R,tag);
t[tag][p].siz=max(t[tag][p<<1].siz,t[tag][p<<1|1].siz);
t[tag][p].num=max(t[tag][p<<1].num,t[tag][p<<1|1].num);
}
ll ask(int p,int L,int R,int op,int tag){
if(L<=t[tag][p].l&&t[tag][p].r<=R){
if(op==0)return t[tag][p].num;
else return t[tag][p].siz;
}
ll val=-1e18;
if(L<=t[tag][p<<1].r)val=max(val,ask(p<<1,L,R,op,tag));
if(R>=t[tag][p<<1|1].l)val=max(val,ask(p<<1|1,L,R,op,tag));
return val;
}
void build(int p,int l,int r){
t[0][p].l=t[1][p].l=l,t[0][p].r=t[1][p].r=r;
t[0][p].num=t[1][p].num=-1e18;
t[0][p].siz=t[1][p].siz=-1e18;
if(l==r)return;
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read(),d[i]=min(b[i],a[i]);
sort(d+1,d+n+1);
sum=unique(d+1,d+n+1)-d-1;
for(int i=1;i<=n;i++){
tmp+=abs(a[i]-b[i]);
if(a[i]