T1
首先可以想到枚举左右端点，桶维护\(c[i]\)出现多少次，\(O(n^2)\)
发现多余枚举因为相同的\(c[i]\)出现多次
考虑如何使相同的\(c[i]\)只被计算常数次
枚举右端点，线段树维护左端点到右端点的欢乐值的最大值
设当前元素颜色为\(c[i]\)，每次只需要将\(c[i]\)上上次出现的位置到\(c[i]\)上次出现的位置减去相应的\(d\)，将\(c[i]\)上次出现的位置到当前位置加上\(d\)
T2
题目里的距离需要\(n^2\)计算，将坐标转换为\((y-x,y+x)\)，两点间距离为\(min(|x_1‘-x_2‘|,|y_1‘-y_2‘| )\)
发现若两个点距离为最小距离，分别和这两个点距离为0的点的集合间也是最小距离
将距离为0的点用并查集维护，将距离最小的两个点所在的并查集连边，去重，对每一条边将两端的\(size\)乘起来累加就行了
代码
T1
#include<bits/stdc++.h>
using namespace std;
const int N=1000011;
struct tree{
long long maxx;
long long lazy;
int l,r;
}tre[5*N];
int n,m,c[N];
int last[N],lastt[N];
long long d[N];
inline int read()
{
int s=0;
char ch=getchar();
while(ch>‘9‘||ch<‘0‘)
ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s;
}
void build(int i,int l,int r)
{
tre[i].l=l;
tre[i].r=r;
if(l==r)
return;
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
return;
}
void pushdown(int i)
{
tre[i<<1].maxx+=tre[i].lazy;
tre[i<<1|1].maxx+=tre[i].lazy;
tre[i<<1].lazy+=tre[i].lazy;
tre[i<<1|1].lazy+=tre[i].lazy;
tre[i].lazy=0;
return;
}
void update(int i)
{
tre[i].maxx=max(tre[i<<1].maxx,tre[i<<1|1].maxx);
return;
}
void insert(int i,int l,int r,long long val)
{
if(tre[i].lazy)
pushdown(i);
if(tre[i].l>=l&&tre[i].r<=r)
{
tre[i].maxx+=val;
tre[i].lazy=val;
return;
}
int mid=(tre[i].l+tre[i].r)>>1;
if(mid>=l)
insert(i<<1,l,r,val);
if(mid<r)
insert(i<<1|1,l,r,val);
update(i);
return;
}
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
c[i]=read();
for(int i=1;i<=m;i++)
d[i]=read();
long long ans=0;
build(1,1,n);
for(int i=1;i<=n;i++)
{
if(last[c[i]])
insert(1,lastt[c[i]]+1,last[c[i]],-d[c[i]]);
insert(1,last[c[i]]+1,i,d[c[i]]);
lastt[c[i]]=last[c[i]];
last[c[i]]=i;
ans=max(ans,tre[1].maxx);
}
cout<<ans<<endl;
return 0;
}
T2
#include<bits/stdc++.h>
using namespace std;
const int N=1000011;
struct pot_{
int x,y;
int num;
}pot[N];
struct bcj{
int x,y;
friend bool operator<(bcj a,bcj b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
}st[N],st1[N];
int n;
int f[N],size[N];
int num,num1;
int minn;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch>‘9‘||ch<‘0‘)
{
if(ch==‘-‘)
w=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
s=(s<<1)+(s<<3)+(ch^48);
ch=getchar();
}
return s*w;
}
bool cmp1(pot_ a,pot_ b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
bool cmp2(pot_ a,pot_ b)
{
return a.y==b.y?a.x<b.x:a.y<b.y;
}
int find(int x)
{
if(f[x]==x)
return x;
return f[x]=find(f[x]);
}
int main()
{
int ans=0;
int x,y;
n=read();
for(int i=1;i<=n;++i)
{
x=read();
y=read();
f[i]=i;
size[i]=1;
pot[i].x=y-x;
pot[i].y=y+x;
pot[i].num=i;
}
minn=0x7fffffff;
sort(pot+1,pot+n+1,cmp1);
for(int i=1;i<n;++i)
{
if(pot[i].x==pot[i+1].x)
{
int f1=find(pot[i].num);
int f2=find(pot[i+1].num);
if(f1!=f2)
{
f[f1]=f2;
size[f2]+=size[f1];
}
}
else
minn=min(minn,abs(pot[i].x-pot[i+1].x));
}
sort(pot+1,pot+n+1,cmp2);
for(int i=1;i<n;++i)
{
if(pot[i].y==pot[i+1].y)
{
int f1=find(pot[i].num);
int f2=find(pot[i+1].num);
if(f1!=f2)
{
f[f1]=f2;
size[f2]+=size[f1];
}
}
else
minn=min(minn,abs(pot[i].y-pot[i+1].y));
}
for(int i=1;i<n;++i)
if(abs(pot[i].y-pot[i+1].y)==minn&&find(pot[i+1].num)!=find(pot[i].num))
{
st[++num].x=find(pot[i].num);
st[num].y=find(pot[i+1].num);
if(st[num].x<st[num].y)
swap(st[num].x,st[num].y);
}
sort(pot+1,pot+n+1,cmp1);
for(int i=1;i<n;i++)
if(abs(pot[i].x-pot[i+1].x)==minn&&find(pot[i].num)!=find(pot[i+1].num))
{
st[++num].x=find(pot[i].num);
st[num].y=find(pot[i+1].num);
if(st[num].x<st[num].y)
swap(st[num].x,st[num].y);
}
sort(st+1,st+num+1);
for(int i=1;i<=num;++i)
if(st[i].x!=st1[num1].x||st[i].y!=st1[num1].y)
{
st1[++num1].x=st[i].x;
st1[num1].y=st[i].y;
}
for(int i=1;i<=num1;i++)
ans+=size[st1[i].x]*size[st1[i].y];
if(!ans)
{
cout<<-1<<endl;
return 0;
}
cout<<minn<<endl;
cout<<ans<<endl;
return 0;
}