点分治
[SDOI2016]模式字符串
点击查看代码
#include
using namespace std;
typedef unsigned long long int ulli;
const ulli base = 31;
const int inf=0x3f3f3f3f;
char in[1000005],tar[1000005];
ulli pows[1000005],hpr[1000005],hsu[1000005];
int s[1000005],t[2000005],nxt[2000005],ban[1000005],cnt;
int dep[1000005],siz[1000005],mxs[1000005],prf[1000005],suf[1000005],sprf[1000005],ssuf[1000005];
int n,m;
unsigned long long ans;
bool vis[1000005];
inline void addedge(int from,int to) {
t[++cnt]=to,nxt[cnt]=s[from],s[from]=cnt;
}
inline void findroot(int pos,const int &fa,const int &fs,int &rt){
siz[pos]=1,mxs[pos]=0;
for(int at=s[pos];at;at=nxt[at])if(t[at]!=fa&&!ban[t[at]]){
findroot(t[at],pos,fs,rt),siz[pos]+=siz[t[at]],mxs[pos]=max(mxs[pos],siz[t[at]]);
}
if((mxs[pos]=max(mxs[pos],fs-siz[pos]))<=mxs[rt])rt=pos;
}
inline void dfs(int pos,int fa,int dep,int &mxd,const char &mid,ulli h){
mxd=max(mxd,dep),h+=in[pos]*pows[dep-1];
if(h==hpr[dep]){
++prf[dep%m];
if(mid==tar[dep%m+1])ans+=ssuf[m-dep%m-1];
}
if(h==hsu[dep]){
++suf[dep%m];
if(mid==tar[m-dep%m])ans+=sprf[m-dep%m-1];
}
for(int at=s[pos];at;at=nxt[at])if(t[at]!=fa&&!ban[t[at]])dfs(t[at],pos,dep+1,mxd,mid,h);
}
inline void solve(int pos,int fs){
if(fs
[JOISC2020] 首都
点击查看代码
#include
using namespace std;
int n,k,rt;
int ver[400005],ne[400005],head[400005],cnt;
bool vis[200005],used[200005],vised[200005];
int col[200005],ans=1e9,tot;
inline int link(int x,int y){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;
}
int siz[200005],mxp[200005];
int find(int x,int fi,int tot){
siz[x]=1;mxp[x]=0;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi||vis[u])continue;
find(u,x,tot);
siz[x]+=siz[u];mxp[x]=max(mxp[x],siz[u]);
}
mxp[x]=max(mxp[x],tot-siz[x]);
if(mxp[x] vec[200005];
queue q;
inline bool push(vector &v){
for(int i=0;i
点分树
[ZJOI2015]幻想乡战略游戏
点击查看代码
#include
using namespace std;
int n,q;
int ver[200005],ne[200005],head[100005],cnt;
long long val[200005];
inline void link(int x,int y,long long v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
int siz[100005],mxp[100005],rt;
bool vis[100005];
void findrt(int x,int fi,int tot){
siz[x]=1;mxp[x]=0;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[u]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[x]=max(mxp[x],siz[u]);
}
mxp[x]=max(mxp[x],tot-siz[x]);
if(mxp[x] >fa[100005];
long long dep[100005],dis[2][100005];
void dfs(int x,int fi,int top){
fa[x].push_back(make_pair(dep[x],top));
siz[x]=1;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[u]||u==fi)continue;
dep[u]=dep[x]+val[i];
dfs(u,x,top);siz[x]+=siz[u];
}
}
set >s[100005];
int up[100005],near[100005];
void build(int x){
vis[x]=1;dep[x]=0;dfs(x,x,x);
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[u])continue;
rt=0;findrt(u,x,siz[u]);up[rt]=x;
build(rt);near[rt]=u;s[x].insert(make_pair(0,rt));
}
}
long long sum[100005],tot;
inline void modify(int x,int v){
long long pre=0;
for(auto it:fa[x]){
dis[0][it.second]+=it.first*v;
if(pre)dis[1][it.second]+=pre;pre=it.first*v;
}
for(auto it:fa[x]){
if(up[it.second]){
int y=it.second,z=up[y];
auto it=s[z].find(make_pair(-sum[y],y));
if(it!=s[z].end())s[z].erase(it);sum[y]+=v;
s[z].insert(make_pair(-sum[y],y));
}else sum[it.second]+=v;
}
}
int find(int x){
if(s[x].empty()||2*sum[s[x].begin()->second]second;long long tmp=sum[x]-sum[u];
modify(near[u],tmp);
int res=find(u);
modify(near[u],-tmp);
return res;
}
inline long long query(int x){
long long res=0,pre=0;
for(auto it:fa[x]){
res+=dis[0][it.second]-dis[1][it.second];
// cout<
#6145. 「2017 山东三轮集训 Day7」Easy
点击查看代码
#include
using namespace std;
int n,m;
int ver[200005],ne[200005],head[100005],cnt;
long long val[200005];
inline void link(int x,int y,long long v){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;val[cnt]=v;
}
int st[21][200005],top,dfn[100005];
long long dep[100005];
void dfs(int x,int fi){
st[0][++top]=x;dfn[x]=top;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(u==fi)continue;
dep[u]=dep[x]+val[i];
dfs(u,x);st[0][++top]=x;
}
}
inline int cmp(int x,int y){
return dep[x]>1]+1;
for(int i=1;i<21;i++){
for(int j=1;j+(1<<(i-1))<=top;j++){
st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
}
inline int lca(int x,int y){
int l=dfn[x],r=dfn[y];
if(l>r)swap(l,r);
int len=lg[r-l+1];
return cmp(st[len][l],st[len][r-(1< q;
inline void bfs(int id){
memset(dis[id],0x3f,sizeof(dis[id]));
for(int i=le[id];i<=ri[id];i++)dis[id][i]=0;
for(int i=le[id];i<=ri[id];i++)q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(dis[id][u]>dis[id][x]+val[i]){
dis[id][u]=dis[id][x]+val[i];
q.push(u);
}
}
}
}
inline int query(int x,int l,int r){
int res=1e9;
for(int i=l;i<=r&&i<=ri[sqr[l]];i++)res=min(res,dist(x,i));
if(sqr[l]==sqr[r])return res;
for(int i=sqr[l]+1;i '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
x *= f;
}
int main(){
Read(n);
for(int i=1;i=1;i--)le[sqr[i]]=i;
for(int i=1;i<=sqr[n];i++)bfs(i);
scanf("%d",&m);
while(m--){
int l,r,x;
Read(l);Read(r);Read(x);
printf("%d\n",query(x,l,r));
}
return 0;
}
[Ynoi2011] 成都七中
点击查看代码
#include
using namespace std;
int n,m;
int col[100005];
int ver[200005],ne[200005],head[100005],cnt;
inline void link(int x,int y){
ver[++cnt]=y;
ne[cnt]=head[x];
head[x]=cnt;
}
int siz[100005],mxp[100005],rt;
bool vis[100005];
void findrt(int x,int fi,int tot){
siz[x]=1;mxp[x]=0;
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[u]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[x]=max(mxp[x],siz[u]);
}
mxp[x]=max(mxp[x],tot-siz[x]);
if(mxp[x] fa[100005],qry[100005];
void dfs(int x,int fi,int l=1e5,int r=0){
l=min(l,x);r=max(r,x);
fa[x].push_back(node(l,r,rt));
qry[rt].push_back(node(l,r,col[x],0));
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[u]||u==fi)continue;
dfs(u,x,l,r);
}
}
void solve(int x){
vis[x]=1;dfs(x,x);
for(int i=head[x];i;i=ne[i]){
int u=ver[i];
if(vis[u])continue;
rt=0;findrt(u,x,siz[u]);
solve(rt);
}
}
int ans[100005];
int tree[100005];
inline void add(int x,int v){
while(x){
tree[x]+=v;
x&=(x-1);
}
}
inline int query(int x){
int res=0;
while(x<=1e5){
res+=tree[x];
x+=(x&-x);
}return res;
}
int pre[100005];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&col[i]);
for(int i=1;i=l&&u.r<=r){
qry[u.x].push_back(node(l,r,i,1));
break;
}
}
}
for(int i=1;i<=n;i++){
sort(qry[i].begin(),qry[i].end());
for(auto it:qry[i]){
if(it.op)ans[it.x]=query(it.l);
else if(pre[it.x]
[WC2014]紫荆花之恋
点击查看代码
#include
using namespace std;
int n,op;
struct BST{
vector b,s,t;
inline void insert(int x){
s.push_back(x);
}
inline void clear(){
b=s=t=vector();
}
inline int query(int x){
if(s.size()>300){
t.resize(b.size()+s.size());
sort(s.begin(),s.end());merge(b.begin(),b.end(),s.begin(),s.end(),t.begin());
swap(b,t);s=vector();
}
int res=upper_bound(b.begin(),b.end(),x)-b.begin();
for(auto it:s)res+=(it<=x);
return res;
}
}bst[2][100005];
vector > vec[100005];
int siz[100005],mxp[100005],rt;
bool vis[100005];
void findrt(int x,int fi,int tot){
siz[x]=1;mxp[x]=0;
for(auto it:vec[x]){
int u=it.first;
if(!vis[u]||u==fi)continue;
findrt(u,x,tot);siz[x]+=siz[u];
mxp[x]=max(mxp[x],siz[u]);
}
mxp[x]=max(mxp[x],tot-siz[x]);
if(mxp[x] son[100005];
vector >fa[100005];
void dfs(int x,int fi,int top){
son[top].push_back(x);
fa[x].push_back(make_pair(top,dep[x]));
for(auto it:vec[x]){
int u=it.first;
if(!vis[u]||u==fi)continue;
dep[u]=dep[x]+it.second;
dfs(u,x,top);
}
}
void build(int x){
vis[x]=0;dep[x]=0;dfs(x,x,x);
for(auto it:vec[x]){
int u=it.first;
if(!vis[u])continue;
rt=0;findrt(u,u,siz[u]);
build(rt);
}
}
inline void solve(int x){
// cout<<"solve "< tmp=son[x];
for(auto it:tmp){
vis[it]=1;dep[it]=0;
son[it]=vector();
while(fa[it].back().first!=x)fa[it].pop_back();fa[it].pop_back();
bst[0][it].clear();bst[1][it].clear();
}
mxp[rt=0]=n;
findrt(x,x,tmp.size());build(rt);
for(auto i:tmp)vis[i]=1;
for(auto i:tmp){
int pre=1e9;
for(auto it:fa[i]){
if(vis[it.first])bst[0][it.first].insert(it.second-r[i]);
if(vis[it.first]&&pre!=1e9)bst[1][it.first].insert(pre);pre=it.second-r[i];
}
}
for(auto i:tmp)vis[i]=0;
}
long long ans,top;
pair stk[100005];
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
inline char gc(){
if(p1==p2){
p1=buf;
p2=buf+fread(buf,1,1000000,stdin);
}
if(p1==p2)return EOF;
return *p1++;
}
inline int read(){
register int res=0;register char c=gc();
register bool is=0;
while(c<'0'||c>'9'){
if(c=='-')is=1;
c=gc();
}
while(c>='0'&&c<='9'){
res=(res<<1)+(res<<3)+(c^48);
c=gc();
}
return is?-res:res;
}
int main(){
op=read();n=read();
{
int a,c;a=read();c=read();r[1]=read();
fa[1].push_back(make_pair(1,0));bst[0][1].insert(-r[1]);son[1].push_back(1);
}puts("0");
for(int i=2;i<=n;i++){
int a,c;
a=read();c=read();r[i]=read();
a^=ans%int(1e9);
vec[a].push_back(make_pair(i,c));vec[i].push_back(make_pair(a,c));
fa[i]=fa[a];for(auto &it:fa[i])it.second+=c;
fa[i].push_back(make_pair(i,0));
int pre=1e9,suf=1e9;top=0;
for(auto it:fa[i]){
son[it.first].push_back(i);stk[++top]=make_pair(it.first,son[it.first].size());
ans+=bst[0][it.first].query(r[i]-it.second);
if(suf!=1e9)ans-=bst[1][it.first].query(suf);suf=r[i]-it.second;
bst[0][it.first].insert(it.second-r[i]);
if(pre!=1e9)bst[1][it.first].insert(pre);pre=it.second-r[i];
}
reverse(stk+1,stk+top+1);
while(top>1){
if(stk[top].second*0.78>=stk[top-1].second)top--;
else {
solve(stk[top].first);top=0;
}
}
printf("%lld\n",ans);
}
return 0;
}
CF936E Iqea
点击查看代码
#include
using namespace std;
const int INF=0x3f3f3f3f;
int n,oc,tc,Q;
vector coors[300005],oe[300005],te[300005],bit[300005][2];
map id[300005];
int bl[300005],ed[300005],xd[300005],bg[300005],mx,total,G;
int yc[300005][30],dis[300005][30],sze[300005],d[300005],fa[300005],vis[300005];
void dfs(int x,int f){
sze[x]=ed[x];
for(int e=te[x].size()-1;e>=0;e--){
int v=te[x][e];
if(v==f||vis[v])continue;
dfs(v,x); sze[x]+=sze[v];
}
}
inline void calcG(int x,int f){
int mxv=total-sze[x];
for(int e=te[x].size()-1;e>=0;e--){
int v=te[x][e];
if(v==f||vis[v])continue;
calcG(v,x);mxv=max(mxv,sze[v]);
}
if(mxv q;
void solve(int x,int f){
fa[x]=f;d[x]=d[f]+1;vis[x]=1;
for(int i=1,o=id[xd[x]][coors[xd[x]][bg[x]]];i<=ed[x];i++,o++){
dis[o][d[x]]=0;yc[o][d[x]]=i;q.push(o);
}
while(!q.empty()){
int u=q.front();q.pop();
for(int e=oe[u].size()-1;e>=0;e--){
int v=oe[u][e];
if(vis[bl[v]]||yc[v][d[x]])continue;
dis[v][d[x]]=dis[u][d[x]]+1;
yc[v][d[x]]=yc[u][d[x]];
q.push(v);
}
}
for(int i=0;i<=ed[x];i++)bit[x][0].push_back(INF),bit[x][1].push_back(INF);
for(int e=te[x].size()-1;e>=0;e--){
int v=te[x][e];
if(vis[v])continue;
dfs(v,x);mx=total=sze[v];
calcG(v,x);solve(G,x);
}
}
inline void inc(vector &a,int p,int v){
for(int i=p;i &a,int p,int v=INF){
for(int i=p;i;i-=(i&(-i)))v=min(v,a[i]);
return v;
}
inline void upt(int o){
for(int j=bl[o];j;j=fa[j]){
inc(bit[j][0],yc[o][d[j]],dis[o][d[j]]-yc[o][d[j]]);
inc(bit[j][1],ed[j]-yc[o][d[j]]+1,dis[o][d[j]]+yc[o][d[j]]);
}
}
inline int ask(int o){
int ans=INF;
for(int j=bl[o];j;j=fa[j]){
ans=min(ans,ask(bit[j][0],yc[o][d[j]])+dis[o][d[j]]+yc[o][d[j]]);
ans=min(ans,ask(bit[j][1],ed[j]-yc[o][d[j]]+1)+dis[o][d[j]]-yc[o][d[j]]);
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
int x,y;scanf("%d%d",&x,&y);
coors[x].push_back(y);
}
for(int i=1;i<300005;i++) {
if(!coors[i].size())continue;
sort(coors[i].begin(),coors[i].end());
coors[i].erase(unique(coors[i].begin(),coors[i].end()),coors[i].end());
for(int p1=0,p2=0;p2