哦我是午夜DJ～我是午夜DJ～快乐时间不能浪费～～～

我是尹鹏哲，我要带领妹子踏平这个世界！！！

我是尹鹏哲，我要带领妹子踏平这个世界！！！！！

#include<bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define db double
#define N 86444
#define rs ((o<<1)|1)
#define ls (o<<1)
#define mid ((l+r)>>1)
using namespace std;
int Min[N*4],lazy[N*4],n;int tag[N];
void down(int o){
if(lazy[o]){
lazy[rs]=Min[rs]=lazy[o];
lazy[ls]=Min[ls]=lazy[o];
lazy[o]=0;
}
}
void Insert(int o,int l,int r,int L,int R,int num){
if(l!=r)down(o);
if(l>=L&&r<=R){if(Min[o]>num)
lazy[o]=Min[o]=num;
return;
}
if(mid<L)Insert(rs,mid+1,r,L,R,num);
else if(mid>=R)Insert(ls,l,mid,L,R,num);
else Insert(rs,mid+1,r,mid+1,R,num),Insert(ls,l,mid,L,mid,num);
Min[o]=min(Min[rs],Min[ls]);
}
int Query(int o,int l,int r,int pos){
if(l==r)return Min[o];
if(mid<pos)return Query(rs,mid+1,r,pos);
else return Query(ls,l,mid,pos);
}
int L,R;
struct s{
int l,r,val;
void read(){
scanf("%d%d%d",&l,&r,&val);
l++,r++;
l=max(l,L);
r=min(R,r);
tag[l]++,tag[r+1]--;
}
}seg[N];
bool comp(const s & a,const s & b){return a.l<b.l;}
int f[N];
int main(){
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
memset(Min,127/3,sizeof(Min));
scanf("%d",&n);scanf("%d%d",&L,&R);L++,R++;
for(int i=1;i<=n;++i)seg[i].read();
int tot(0);for(int i=L;i<=R;++i){
tot+=tag[i];
if(!tot)cout<<"-1",exit(0);
}
sort(seg+1,seg+n+1,comp);
int n1=1;
for(int i=L-1;i<=R;++i){
if(i!=L-1)f[i]=Query(1,1,N-1,i);
while(i==seg[n1].l-1)
Insert(1,1,N-1,seg[n1].l,seg[n1].r,f[min(i,0)]+seg[n1].val),n1++;
}cout<<f[R];
return 0;
}

回复 @MayLava :
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define N 100010
#define lowbit ( (i) & (-i) )
#define LL long long
using namespace std;
struct point{
int x,y;
void read(){scanf("%d%d",&x,&y);}
}p[N];
struct seg{
int h1,h2,h3,flag;
seg() {}
seg(int x,int y,int z,int a):h1(x),h2(y),h3(z),flag(a) {}
}s[N];
int tree[N],n,tot,sz,sub[N];
void Insert(int pos,int num){for(int i=pos;i<N;i+=lowbit)tree[i]+=num;}
int Query(int pos){int sum(0);for(int i=sum;i;i-=lowbit)sum+=tree[i];return sum;}
int find(int x){
return lower_bound(sub+1,sub+sz+1,x)-sub;
}
void link(int ff,int l,int r,int h){//0横线，//1竖线
if(!ff){
s[++tot]=seg(find(l),find(r),h,0);
}else {
int X=find(h);
s[++tot]=seg(X,X,l,1);
s[++tot]=seg(X,X,r,-1);
}
}
bool comp(const point & a,const point & b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool Comp(const point & a,const point & b){return a.y==b.y?a.x<b.x:a.y<b.y;}
bool COMP(const seg & a,const seg & b){
if(a.h3!=b.h3)return a.h3<b.h3;
return a.flag<b.flag;
}
void build(){
sort(p+1,p+n+1,comp);
for(int i=2;i<=n;++i)
if(p[i].x==p[i-1].x)
link(1,p[i-1].y,p[i].y,p[i].x);
sort(p+1,p+n+1,Comp);
for(int i=2;i<=n;++i)
if(p[i].y==p[i-1].y)
link(0,p[i-1].x,p[i].x,p[i].y);
sort(s+1,s+tot+1,COMP);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)p[i].read(),sub[++sub[0]]=p[i].x;
sort(sub+1,sub+sub[0]+1);
sz=unique(sub+1,sub+sub[0]+1)-sub-1;
build();LL Ans(0);
for(int i=1;i<=tot;++i){
if(!s[i].flag)Ans+=Query(s[i].h2)-Query(s[i].h1-1);
else {
Insert(s[i].h1,s[i].flag);
}
}cout<<Ans;
return 0;
}

加了氧气还慢一些是为什么

#include<bits/stdc++.h>
#define N 3010
using namespace std;
struct ed{int nxt,to;}e[N];
int head[N],tot,w[N],n,rt,dp[N][N],k;
void add(int u,int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}
void DP(int u,int cnt){if(!cnt)return;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v=e[i].to;
for(int j=1;j<=cnt;++j)dp[v][j]=dp[u][j];DP(v,cnt-1);
for(int j=cnt;j>=1;j--)dp[u][j]=max(dp[u][j],dp[v][j-1]+w[v]);
}
}
int main(){
freopen("knapsack.in","r",stdin);
freopen("knapsack.out","w",stdout);
memset(head,-1,sizeof(head));cin>>n>>k;int zz;
for(int i=1;i<=n;++i){
cin>>zz;if(zz)add(zz,i);
else rt=i;
}for(int i=1;i<=n;++i)cin>>w[i];DP(rt,k);
cout<<dp[rt][k-1]+w[rt];
return 0;
}

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define inf (1<<30)
#define il inline
#define RG register
#define LL long long
#define lowbit(o) o & (-o)
#define N 40001
using namespace std;
struct ed{int nxt,to;}e[N*2];int head[N],tot;
int id[N],top[N],BL[N],sz[N],fa[N],deep[N],hson[N],w[N];
int n,P,Q,idn;
inline int read() {
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
il void add(RG int u,RG int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}
il void ADD(RG int u,RG int v){add(u,v),add(v,u);}
il void dfs1(RG int u,RG int faa){
deep[u]=deep[faa]+1,sz[u]=1;fa[u]=faa;
for(RG int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=faa){
RG int v=e[i].to;dfs1(v,u);
sz[u]+=sz[v];if(sz[hson[u]]<sz[v])hson[u]=v;
}
}
il void dfs2(RG int u,RG int toop){top[u]=toop;
id[u]=++idn;BL[idn]=u;if(hson[u])dfs2(hson[u],toop);
for(RG int i=head[u];i!=-1;i=e[i].nxt)
if(e[i].to!=fa[u]&&e[i].to!=hson[u])
dfs2(e[i].to,e[i].to);w[u]=idn;
}
il int LCA(RG int x,RG int y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=fa[top[x]];
}if(deep[x]>deep[y])swap(x,y);
return x;
}
il int gogogo(int x,int y){RG int ll=0;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
ll=top[x],x=fa[top[x]];
}if(deep[x]>deep[y])swap(x,y);
return x==y?ll:BL[id[x]+1];
}
struct matrix{
int x,xx,y,yy,k;
matrix() {}
matrix(int X,int XX,int Y,int YY,int K):x(X),xx(XX),y(Y),yy(YY),k(K) {}
}p[N*2];int cnt;
struct node{
int x,y,k,id;
node() {}
node(int _x,int _y,int _k,int i):x(_x),y(_y),k(_k),id(i) {}
}ff[N],quer[N],quel[N];
int tree[N],ans[N];
il void Add(int x,int y){for(RG int i=x;i<=n;i+=lowbit(i))tree[i]+=y;}
int Query(int x){int s=0;for(RG int i=x;i;i-=lowbit(i))s+=tree[i];return s;}
il bool comp(const matrix & a,const matrix & b){return a.k<b.k;}
struct ha{
int x,y,yy,v,kind;
ha() {}
ha(int a,int b,int c,int d,int e):x(a),y(b),yy(c),v(d),kind(e) {}
}que[N*3];int sum[N];
il bool Comp(const ha & a,const ha & b){return a.x==b.x?a.kind<b.kind:a.x<b.x;}
il void solve(RG int h,RG int t,RG int l,RG int r){
if(t<h)return;
if(l==r){
for(int i=h;i<=t;++i)ans[ff[i].id]=p[l].k;
return;
}RG int mid=(l+r)>>1;int ss=0;
for(RG int i=l;i<=mid;++i){
que[++ss]=ha(p[i].x,p[i].y,p[i].yy,1,0);
que[++ss]=ha(p[i].xx,p[i].y,p[i].yy,-1,n+1);
}for(RG int i=h;i<=t;++i)
que[++ss]=ha(ff[i].x,ff[i].y,0,0,i);
sort(que+1,que+ss+1,Comp);memset(tree,0,sizeof(tree));
for(RG int i=1;i<=ss;++i)
if(que[i].kind>=h&&que[i].kind<=t)
sum[que[i].kind]=Query(que[i].y);
else Add(que[i].y,que[i].v),Add(que[i].yy+1,-que[i].v);
RG int L=0,R=0;
for(RG int i=h;i<=t;++i){
if(sum[i]>=ff[i].k)quel[++L]=ff[i];
else quer[++R]=ff[i],quer[R].k-=sum[i];
}for(RG int i=1;i<=L;++i)ff[i+h-1]=quel[i];
for(RG int i=1;i<=R;++i)ff[L+h+i-1]=quer[i];
solve(h,h+L-1,l,mid);solve(h+L,t,mid+1,r);
}
int main(){
freopen("fruit_hnoi2015.in","r",stdin);
freopen("fruit_hnoi2015.out","w",stdout);
memset(head,-1,sizeof(head));
n=read(),P=read(),Q=read();int u,v;
for(RG int i=1;i<n;++i)u=read(),v=read(),ADD(u,v);
dfs1(1,1),dfs2(1,1);
for(RG int i=1;i<=P;++i){
RG int a,b,c;a=read(),b=read(),c=read();
RG int lca=LCA(a,b);if(id[a]>id[b])swap(a,b);
if(lca==a){RG int mm=gogogo(a,b);
if(id[mm]>1)p[++cnt]=matrix(1,id[mm]-1,id[b],w[b],c);
if(w[mm]+1<=n)p[++cnt]=matrix(id[b],w[b],w[mm]+1,n,c);
}
else p[++cnt]=matrix(id[a],w[a],id[b],w[b],c);
}
for(RG int i=1;i<=Q;++i){
RG int u,v,k;u=read(),v=read(),k=read();
if(id[u]>id[v])swap(u,v);
ff[i]=node(id[u],id[v],k,i);
}sort(p+1,p+cnt+1,comp);solve(1,Q,1,cnt);
for(RG int i=1;i<=Q;++i)cout<<ans[i]<<"\n";
return 0;
}

我是卿云鹏，我要带领数千万巨人踏平这个世界！！！

Tarjan+SPFA+dp