T1 送花

线段树。枚举右端点，线段树记录左端点对应的值。

每次对当前颜色上上次出现的位置到上次出现的位置区间减，上次出现的位置到当前位置区间加。

$code:$

 1 #include<bits/stdc++.h>

 2 #define LL long long

 3 using namespace std;

 4 const int NN=1e6+5;

 5 int n,m,c[NN],d[NN],pre[NN][2];

 6 LL ans;

 7 inline int read(){

 8     int x=0,f=1; char ch=getchar();

 9     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11     return x*f;

12 }

13 inline void write(LL x,char sp){

14     char ch[20]; int len=0;

15     if(x<0){ putchar('-'); x=~x+1; }

16     do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

17     for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

18 }

19 struct segment_tree{

20     #define ld rt<<1

21     #define rd (rt<<1)|1

22     LL mx[NN<<2],laz[NN<<2];

23     void pushup(int rt){

24         mx[rt]=max(mx[ld],mx[rd]);

25     }

26     void pushdown(int rt){

27         if(!laz[rt]) return;

28         laz[ld]+=laz[rt]; laz[rd]+=laz[rt];

29         mx[ld]+=laz[rt]; mx[rd]+=laz[rt];

30         laz[rt]=0;

31     }

32     void modify(int rt,int l,int r,int opl,int opr,int val){

33         if(l>=opl&&r<=opr){

34             mx[rt]+=val;

35             laz[rt]+=val;

36             return;

37         }

38         pushdown(rt);

39         int mid=(l+r)>>1;

40         if(opl<=mid) modify(ld,l,mid,opl,opr,val);

41         if(opr>mid) modify(rd,mid+1,r,opl,opr,val);

42         pushup(rt);

43     }

44     LL query(int rt,int l,int r,int opl,int opr){

45         if(l>=opl&&r<=opr) return mx[rt];

46         pushdown(rt);

47         int mid=(l+r)>>1;

48         LL ans=0;

49         if(opl<=mid) ans=max(ans,query(ld,l,mid,opl,opr));

50         if(opr>mid) ans=max(ans,query(rd,mid+1,r,opl,opr));

51         return ans;

52     }

53 }s;

54 signed main(){

55     n=read(); m=read();

56     for(int i=1;i<=n;i++) c[i]=read();

57     for(int i=1;i<=m;i++) d[i]=read();

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

59         if(pre[c[i]][0]) s.modify(1,1,n,pre[c[i]][1]+1,pre[c[i]][0],-d[c[i]]);

60         s.modify(1,1,n,pre[c[i]][0]+1,i,d[c[i]]);

61         ans=max(ans,s.query(1,1,n,1,n));

62         pre[c[i]][1]=pre[c[i]][0]; pre[c[i]][0]=i;

63     }

64     write(ans,'\n');

65     return 0;

66 }

T2 星空

并查集合并距离为零的点，$O(n^2)$有$70pts$。

考虑优化。发现令$b=x+y$，$B=x-y$，那么两个点的直接距离其实为$min(|b_i-b_j|,|B_i-B_j|)$。

于是可以排序后扫一遍得出答案。点对数只要去重后将两个符合条件的并查集大小相乘后累加。

注意排序后点集的下标改变，所有并查集操作都要通过$id$来实现。

$code:$

 1 #include<bits/stdc++.h>

 2 #define mp make_pair

 3 using namespace std;

 4 const int NN=1e5+5;

 5 int n,x[NN],y[NN],fa[NN],siz[NN],ans=INT_MAX,num;

 6 map<pair<int,int>,bool>vis;

 7 vector<pair<int,int> >vec;

 8 struct loc{ int x,y,b1,b2,id; }l[NN];

 9 inline bool cmp1(loc a,loc b){ return a.b1<b.b1; }

10 inline bool cmp2(loc a,loc b){ return a.b2<b.b2; }

11 inline int getfa(int x){ return fa[x]==x?x:fa[x]=getfa(fa[x]); }

12 inline int read(){

13     int x=0,f=1; char ch=getchar();

14     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

15     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

16     return x*f;

17 }

18 inline void write(int x,char sp){

19     char ch[20]; int len=0;

20     if(x<0){ putchar('-'); x=~x+1; }

21     do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

22     for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

23 }

24 void merge(int x,int y){

25     x=getfa(x); y=getfa(y);

26     if(x==y) return;

27     fa[y]=x; siz[x]+=siz[y];

28 }

29 signed main(){

30     n=read();

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

32         l[i].x=read(); l[i].y=read();

33         fa[i]=i; siz[i]=1; l[i].id=i;

34         l[i].b1=l[i].y-l[i].x;

35         l[i].b2=l[i].y+l[i].x;

36     }

37     sort(l+1,l+n+1,cmp1);

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

39         if(l[i].b1==l[i+1].b1) merge(l[i].id,l[i+1].id);

40     sort(l+1,l+n+1,cmp2);

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

42         if(l[i].b2==l[i+1].b2) merge(l[i].id,l[i+1].id);

43     sort(l+1,l+n+1,cmp1);

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

45         if(getfa(l[i].id)==getfa(l[i+1].id)) continue;

46         if(l[i+1].b1==l[i].b1) continue;

47         if(ans>=l[i+1].b1-l[i].b1){

48             if(ans>l[i+1].b1-l[i].b1) vec.clear();

49             vec.push_back(mp(getfa(l[i].id),getfa(l[i+1].id)));

50             ans=l[i+1].b1-l[i].b1;

51         }

52     }

53     sort(l+1,l+n+1,cmp2);

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

55         if(getfa(l[i].id)==getfa(l[i+1].id)) continue;

56         if(l[i+1].b2==l[i].b2) continue;

57         if(ans>=l[i+1].b2-l[i].b2){

58             if(ans>l[i+1].b2-l[i].b2) vec.clear();

59             vec.push_back(mp(getfa(l[i].id),getfa(l[i+1].id)));

60             ans=l[i+1].b2-l[i].b2;

61         }

62     }

63     if(vec.empty()){ puts("0"); return 0;}

64     for(int i=0;i<vec.size();i++){

65         if(vis[vec[i]]) continue;

66         vis[vec[i]]=1;

67         vis[mp(vec[i].second,vec[i].first)]=1;

68         num+=siz[vec[i].first]*siz[vec[i].second];

69     }

70     write(ans,'\n'); write(num,'\n');

71     return 0;

72 }

T3 零一串

因为不可抗力詁了（连咕两场的怠惰罪该万死

巴特西

2021.8.15考试总结[NOIP模拟40]

T1 送花

T2 星空

T3 零一串

最新文章

热门文章