T1
记当前位置 \(i\) 上的颜色，上次出现的位置为 \(last_{1}\) ，上上次出现的位置为 \(last_{2}\) ，则，把当前点的颜色加进来，并且让其产生贡献的话，则会对 \([last_{2}+1,last_{1}]\) ，造成 \(-val_{i}\) 的贡献，对 \([last_{1}+1,i]\) 造成 \(val_{i}\) 的贡献。
发现就是个区间加，用线段树维护，每次加入新颜色后的最大值就是 \(1\) 号节点所存储的信息。
Code
#include<cstdio>
#define MAX 1000010
#define re register
#define int64_t long long
namespace OMA
{
int n,m,c[MAX],d[MAX],last[MAX][2];
template<typename type>inline type max(type a,type b)
{ return a>b?a:b; }
struct Segment_Tree
{
struct TREE
{
//int l,r;
int64_t xam;
int64_t lazy;
}st[MAX<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
#define mid(p) (lp+rp>>1)
inline void Push_up(int p)
{ st[p].xam = max(st[ls(p)].xam,st[rs(p)].xam); }
inline void Push_down(int p)
{
if(st[p].lazy)
{
st[ls(p)].xam += st[p].lazy;
st[rs(p)].xam += st[p].lazy;
st[ls(p)].lazy += st[p].lazy;
st[rs(p)].lazy += st[p].lazy;
st[p].lazy = 0;
}
}
/*inline void build(int p,int l,int r)
{
st[p].l = l,st[p].r = r;
if(l==r)
{ return ; }
build(ls(p),l,mid(p)),build(rs(p),mid(p)+1,r);
}*/
inline void update(int p,int l,int r,int val,int lp,int rp)
{
if(l<=lp&&rp<=r)
{ st[p].xam += val,st[p].lazy += val; return ; }
Push_down(p);
if(l<=mid(p))
{ update(ls(p),l,r,val,lp,mid(p)); }
if(r>mid(p))
{ update(rs(p),l,r,val,mid(p)+1,rp); }
Push_up(p);
}
}Tree;
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
int w=1; s=0; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*=w,*this;
}
}cin;
signed main()
{
cin >> n >> m;
for(re int i=1; i<=n; i++)
{ cin >> c[i]; }
for(re int i=1; i<=m; i++)
{ cin >> d[i]; }
//Tree.build(1,1,n);
int64_t ans = 0;
for(re int i=1; i<=n; i++)
{
if(last[c[i]][0])
{
Tree.update(1,last[c[i]][0]+1,last[c[i]][1],-d[c[i]],1,n);
Tree.update(1,last[c[i]][1]+1,i,d[c[i]],1,n);
}
else if(last[c[i]][1])
{
Tree.update(1,1,last[c[i]][1],-d[c[i]],1,n);
Tree.update(1,last[c[i]][1]+1,i,d[c[i]],1,n);
}
else
{ Tree.update(1,1,i,d[c[i]],1,n); }
last[c[i]][0] = last[c[i]][1];
last[c[i]][1] = i;
//printf("max now := %lld\n",Tree.st[1].xam);
ans = max(ans,Tree.st[1].xam);
}
printf("%lld\n",ans);
return 0;
}
}
signed main()
{ return OMA::main(); }
T2
发现最优的且非0的距离，肯定是一个点经过了一个跟它距离为0的点，到达了另一个点。
考虑将坐标系旋转45度，则原先点的坐标变成了 \((\frac{\sqrt{2}(x-y)}{2},\frac{\sqrt{2}(x+y)}{2})\) ，为了方便，直接在此乘上一个 \(\sqrt{2}\) ，这样算答案时就不用再乘了，坐标转换在读入时就可以完成。
转换完坐标后，此题答案就是 \(\min((x-y),(x+y))\) 。
考虑按 \(x\) 排序，将 \(x\) 相等的放进一个集合中，表示这些点之间的距离为 \(0\) 。
再按 \(y\) 排序，同样将 \(y\) 相等的放进一个集合。
上面两步可以用并查集实现。
找最小值，就再按 \(x\) 排一遍序，找第一个跟它u不在一个集合内的更新答案，并将满足最小答案的都记下来，同样的，按 \(y\) 再做一边。
最后统计对数，就是合法的集合的大小相乘即可，记得去重。
Code
#include<vector>
#include<cstdio>
#include<algorithm>
#define MAX 100010
#define re register
#define INF 2147483647
using std::sort;
using std::unique;
using std::vector;
using std::pair;
using std::make_pair;
namespace OMA
{
int n,cnt,ans=INF;
struct my
{ int x,y,id; }p[MAX];
vector<pair<int,int>>edge;
inline bool cmp1(const my &a,const my &b)
{ return a.x<b.x; }
inline bool cmp2(const my &a,const my &b)
{ return a.y<b.y; }
inline int abs(int a)
{ return a>=0?a:-a; }
inline int min(int a,int b)
{ return a<b?a:b; }
int fa[MAX],size[MAX];
inline int find(int x)
{ return x!=fa[x]?fa[x] = find(fa[x]):x; }
inline void merge(int x,int y)
{
int r1 = find(x),r2 = find(y);
if(r1!=r2)
{
fa[r1] = r2;
size[r2] += size[r1];
}
}
inline void solve()
{
for(re int i=1; i<=n-1; i++)
{
for(re int j=i+1,r1,r2; j<=n; j++)
{
if((r1 = find(fa[p[i].id])) != (r2 = find(fa[p[j].id])))
{
int now = min(abs(p[i].x-p[j].x),abs(p[i].y-p[j].y));
if(now<=ans)
{
if(now<ans)
{ edge.clear(); ans = now; }
edge.push_back(make_pair(r1,r2));
edge.push_back(make_pair(r2,r1));
}
break ;
}
}
}
}
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
int w=1; s=0; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*=w,*this;
}
}cin;
signed main()
{
//freopen("node.in","r",stdin);
cin >> n;
for(re int i=1,x,y; i<=n; i++)
{
fa[i] = i,size[i] = 1;
cin >> x >> y; p[i] = (my){x-y,x+y,i};
}
sort(p+1,p+1+n,cmp1);
for(re int i=1; i<=n-1; i++)
{
if(p[i].x==p[i+1].x)
{ merge(p[i].id,p[i+1].id); }
}
sort(p+1,p+1+n,cmp2);
for(re int i=1; i<=n-1; i++)
{
if(p[i].y==p[i+1].y)
{ merge(p[i].id,p[i+1].id); }
}
sort(p+1,p+1+n,cmp1); solve();
sort(p+1,p+1+n,cmp2); solve();
if(ans==INF)
{ printf("-1\n"); }
else
{
sort(edge.begin(),edge.end());
edge.erase(unique(edge.begin(),edge.end()),edge.end());
for(re int i=0; i<edge.size(); i++)
{ cnt += size[edge[i].first]*size[edge[i].second]; }
printf("%d\n%d\n",ans,cnt/2);
}
return 0;
}
}
signed main()
{ return OMA::main(); }
T3
小心CE
int64_t bin[MAX]={1};