目录
hdu1 04 Ball（bitset）
把所有边升序排序后，枚举中间大小的边\(e\)
考虑对每个点\(i\)记录所有\(dis(i,j)\le e\)的\(j\)构成的集合\(S_i\)
在枚举到边\((u,v,w)\)时，以该边为中位数的三角形答案为\(S_i \cap \bar{S_j}\)
利用bitset容易维护
#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define Fill(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf=2139062143;
const int MOD=998244353;
const int MAXN=2010;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace CALC
{
inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
inline int mns(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int mul(int a,int b){return (1LL*a*b)%MOD;}
inline void inc(int &a,int b){a=pls(a,b);}
inline void dec(int &a,int b){a=mns(a,b);}
inline void tms(int &a,int b){a=mul(a,b);}
inline int qp(int x,int t,int res=1)
{for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;}
inline int Inv(int x){return qp(x,MOD-2);}
}
using namespace CALC;
const int lim=200100;
int n,m,ntp[lim];
ll ans;
pii p[MAXN];
struct Edge{int w,x,y;};
bool operator < (const Edge &a,const Edge &b){return a.w<b.w;}
vector<Edge> v;
bitset<MAXN> cur[MAXN];
inline int dis(const pii &a,const pii &b)
{
return abs(a.first-b.first)+abs(a.second-b.second);
}
void init(int n=2e5)
{
ntp[1]=1;
rep(i,2,n) rep(j,2,n/i) ntp[i*j]=1;
}
int main()
{
init();
rep(T,1,read())
{
n=read(),m=read(),ans=0;
rep(i,1,n) p[i].first=read(),p[i].second=read();
v.clear();
rep(i,1,n) rep(j,i+1,n) v.push_back({dis(p[i],p[j]),i,j});
sort(v.begin(),v.end());
rep(i,1,n) cur[i].reset();
for(auto t:v)
{
int i=t.x,j=t.y;
if(!ntp[t.w])ans+=(cur[i]^cur[j]).count();
cur[i][j]=1,cur[j][i]=1;
}
printf("%lld\n",ans);
}
}
hdu1 07 Treasure（重构树+树状数组）
挺套路的但是板子有点多
先建克鲁斯卡尔重构树，这样查询即为子树查询
因为每个颜色的点数很少，对每个颜色建虚树后暴力向上更新，树状数组维护一下即可
（因为hdu特性这题需要略微卡一卡常数，下面的代码有一定概率在hdu上通过
一开始写了个树剖树状数组的\(\log^2\)复杂度的然后过不去，改成\(10\log\)还是过不去，然而事实上在本地这两个算法跑的差不多快。
#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define Fill(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf=2139062143;
const int MOD=998244353;
const int MAXN=200100;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace CALC
{
inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
inline int mns(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int mul(int a,int b){return (1LL*a*b)%MOD;}
inline void inc(int &a,int b){a=pls(a,b);}
inline void dec(int &a,int b){a=mns(a,b);}
inline void tms(int &a,int b){a=mul(a,b);}
inline int qp(int x,int t,int res=1)
{for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;}
inline int Inv(int x){return qp(x,MOD-2);}
}
using namespace CALC;
int n,m,q,col[MAXN],val[MAXN],fa[MAXN],tot,lim[MAXN];
int dep[MAXN],dfn,bl[MAXN],hvs[MAXN],sz[MAXN],in[MAXN];
int G[MAXN][2],f[MAXN][18];
vi vec[MAXN];
struct Edge{int u,v,w;}e[MAXN];
bool operator < (const Edge &x,const Edge &y){return x.w<y.w;}
bool cmp(int a,int b){return in[a]<in[b];}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int u,int v,int w)
{
int fu=find(u),fv=find(v);
if(fu!=fv)
{
lim[++tot]=w,val[tot]=0;
fa[fu]=fa[fv]=tot;
G[tot][0]=fu;
G[tot][1]=fv;
}
}
namespace Fenwick
{
ll c[MAXN];
void mem(int lim){rep(i,1,lim) c[i]=0;}
void mdf(int x,int w){for(;x<=tot;x+=x&-x) c[x]+=w;}
ll getw(int x,ll res=0){for(;x;x-=x&-x) res+=c[x];return res;}
ll query(int x){return getw(in[x]+sz[x]-1)-getw(in[x]-1);}
}
void kruskal()
{
sort(e+1,e+m+1);
rep(i,1,m) merge(e[i].u,e[i].v,e[i].w);
}
int getanc(int x,int w)
{
dwn(i,17,0) if(lim[f[x][i]]<=w) x=f[x][i];
return x;
}
void dfs(int x,int pa)
{
fa[x]=pa,sz[x]=1,dep[x]=dep[pa]+1;
f[x][0]=pa;
for(int i=1;(1<<i)<dep[x];++i)
f[x][i]=f[f[x][i-1]][i-1];
if(!G[x][0]) return ;
for(auto v:G[x])
{dfs(v,x);sz[x]+=sz[v];if(sz[v]>sz[hvs[x]]) hvs[x]=v;}
}
void Dfs(int x,int anc)
{
bl[x]=anc,in[x]=++dfn;
if(!hvs[x]) return ;
Dfs(hvs[x],anc);
for(auto v:G[x]) if(v^hvs[x]) Dfs(v,v);
}
int lca(int x,int y)
{
for(;bl[x]!=bl[y];x=fa[bl[x]])
if(dep[bl[x]]<dep[bl[y]]) swap(x,y);
return in[x]<in[y]?x:y;
}
unordered_map<int,int> lnk[MAXN];
unordered_map<int,ll> mx[MAXN];
int st[MAXN],tp;
ll sum[MAXN];
void addedge(int col,int u,int v)
{
lnk[col][v]=u;
if(!mx[col].count(v)) mx[col][v]=val[v];
mx[col][u]=max(mx[col][u],mx[col][v]);
sum[u]+=mx[col][v];
}
void ins(int col,int x)
{
if(tp==1) {st[++tp]=x;return ;}
int y=lca(x,st[tp]);
if(st[tp]==y) return ;
while(tp>1&&in[st[tp-1]]>=in[y]) addedge(col,st[tp-1],st[tp]),tp--;
if(y!=st[tp]) addedge(col,y,st[tp]),st[tp]=y;
st[++tp]=x;
}
void solve()
{
n=tot=read(),m=read(),q=read();
rep(i,1,n) col[i]=read(),vec[col[i]].push_back(i);
rep(i,1,n) val[i]=read();
rep(i,1,m) e[i].u=read(),e[i].v=read(),e[i].w=read();
rep(i,1,n<<1) fa[i]=i,lim[i]=0,hvs[i]=0;
lim[0]=inf;
Fill(f,0);dfn=0;
kruskal();
dfs(tot,0);Dfs(tot,tot);
Fenwick::mem(tot);
rep(i,1,n) if(vec[i].size())
{
sort(vec[i].begin(),vec[i].end(),cmp);
st[tp=1]=tot;
for(auto x:vec[i]) ins(i,x);
while(tp>1) addedge(i,st[tp-1],st[tp]),tp--;
lnk[i][tot]=0;
for(auto t:mx[i])
Fenwick::mdf(in[t.first],t.second-sum[t.first]),sum[t.first]=0;
}
while(q--)
{
int op=read(),x=read();ll y=read();
if(!op)
{
int c=col[x];
Fenwick::mdf(in[x],y);
y+=mx[c][x];
for(int pa;pa=lnk[c][x];x=lnk[c][x])
{
Fenwick::mdf(in[pa],max(0LL,y-mx[c][pa])-y+mx[c][x]);
mx[c][x]=y;
if(y<=mx[c][pa]) break;
}
if(x==tot) mx[c][x]=y;
}
else
printf("%lld\n",Fenwick::query(getanc(x,y)));
}
rep(i,1,n) vec[i].clear(),lnk[i].clear(),mx[i].clear();
rep(i,1,tot) G[i][0]=G[i][1]=0;
}
int main()
{
rep(T,1,read()) solve();
}
hdu8 07 Darnassus（根号乱搞+最小生成树）
发现一定存在一个最大边权小于等于\(n-1\)的生成树，因此只需要对所有边权小于等于\(n-1\)的边做最小生成树
用根号的复杂度分别枚举\(idx\)和\(p_idx\)的差即可得到所有满足要求的边
再利用桶排序做\(kruskal\)即可
（有些卡常
#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define Fill(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf=2139062143;
const int MOD=998244353;
const int MAXN=50100;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline ll readll()
{
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
namespace CALC
{
inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
inline int mns(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int mul(int a,int b){return (1LL*a*b)%MOD;}
inline void inc(int &a,int b){a=pls(a,b);}
inline void dec(int &a,int b){a=mns(a,b);}
inline void tms(int &a,int b){a=mul(a,b);}
inline int qp(int x,int t,int res=1)
{for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;}
inline int Inv(int x){return qp(x,MOD-2);}
}
using namespace CALC;
int n,m,p[MAXN],q[MAXN],vis[MAXN],fa[MAXN],ans;
int fst[MAXN],nxt[MAXN*450],cnt,p1[MAXN*450],p2[MAXN*450];
void add(int w,int u,int v)
{
nxt[++cnt]=fst[w],fst[w]=cnt,p1[cnt]=u,p2[cnt]=v;
}
inline int calc(int i,int j){return abs(i-j)*abs(p[i]-p[j]);}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void solve()
{
scanf("%d",&n);m=ans=cnt=0;
rep(i,1,n) {scanf("%d",&p[i]);q[p[i]]=i;fa[i]=i;}
rep(i,1,n-1) fst[i]=0;
int lim=sqrt(n-0.5);
rep(i,1,n)
{
rep(j,i+1,min(i+lim,n))
if(calc(i,j)<n) add(calc(i,j),i,j);
rep(j,p[i]+1,min(p[i]+lim,n))
if(calc(i,q[j])<n)
add(calc(i,q[j]),i,q[j]);
}
rep(i,1,n-1)
{
for(int j=fst[i];j;j=nxt[j])
{
int x=find(p1[j]),y=find(p2[j]);
if(x!=y)
{
fa[x]=y,ans+=i;
if((++m)==n-1) {printf("%d\n",ans);return ;}
}
}
}
}
int main()
{
rep(T,1,read()) solve();
}