听说这是JSOIDay6（为什么江苏有这么多省选）
膜了贵省的题目，感到不明觉厉。
T1
这是一道人类智慧题。（其实是窝想错了）
考试时不断YY费用流的模型。（其实是被Gold_7误导了）
然而这是一道区间dp。
把每个敌人抽象为左端点为ai，右端点为bi，高度为ci的线段。
对于区间[l,r]，找到其中最高的线段，枚举上面的点，然后用一条直线切断它以及它下方可以切断的点，那么就阔以转移辣！
T2
这是一道难题。（其实是因为gonens不会做）
那么就介绍一下60分蒜法：枚举根，dfs，然后在线段树上修改和询问就阔以辣！
（然而窝忘记开longlong了）
T3
这是一道码农题。（其实是窝写得臭）
考试的时候发现在线是用来搞笑的。
后来正解说明在线确实是用来搞笑的。
首先从大到小枚举边，并查集维护连通性，如果不在同一个集合里就直接加上去，否则找到环上最大的边，删去。
接着用可持久化线段树维护一下选择的边。
最后对于区间[l,r]就是在编号为l的线段树上询问[l,r]。
（然而其中的离散实在是太蛋疼了）
[Codes]
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1010;
int cas,n,i,j,k,p,cnt;
int a[M],b[M],c[M],g[M],A[M],f[M][M];
int main(){
memset(f,0,sizeof f);
scanf("%d",&n);
cnt=0;
for (i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]),A[++cnt]=a[i],A[++cnt]=b[i];
sort(A+1,A+cnt+1);
cnt=unique(A+1,A+cnt+1)-A-1;
for (i=1;i<=n;i++)a[i]=lower_bound(A+1,A+cnt+1,a[i])-A,b[i]=lower_bound(A+1,A+cnt+1,b[i])-A;
for (p=1;p<cnt;p++)
for (i=1;i<=cnt-p;i++){
memset(g,0,sizeof g);
int j=i+p,mx=0;
f[i][j]=1000000007;
for (k=1;k<=n;k++)
if (a[k]>=i&&b[k]<=j&&c[k]>mx)mx=c[k];
if (!mx){f[i][j]=0;continue;}
for (k=1;k<=n;k++)
if (a[k]>=i&&b[k]<=j&&c[k]==mx)g[b[k]+1]--,g[a[k]]++;
for (k=i+1;k<=j;k++)g[k]+=g[k-1];
for (k=i;k<=j;k++)
if (g[k]>0)f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+mx);
}
printf("%d\n",f[1][cnt]);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1000010;
const int M=5010;
long long ans1;
int n,i,x,y,ch,edgenum,ans2;
int head[M],vet[M],next[M],len[M],flag[M];
int tree[maxn*4];
void addedge(int x,int y,int ch){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
len[edgenum]=ch;
}
int query(int x,int l,int r,int p){
if (l==r)return l;
int mid=l+r>>1;
if (tree[p<<1]>=x)return query(x,l,mid,p<<1);
else return query(x-tree[p<<1],mid+1,r,p<<1|1);
}
void update(int x,int l,int r,int p,int t){
tree[p]+=t;
if (l==r)return;
int mid=l+r>>1;
if (x<=mid)update(x,l,mid,p<<1,t);
else update(x,mid+1,r,p<<1|1,t);
}
void dfs(int u,int dep){
int e,v;
flag[u]=1;
if (dep&1)ans1+=query(dep/2+1,1,maxn,1),ans2++;
for (e=head[u];e;e=next[e]){
v=vet[e];
if (flag[v])continue;
update(len[e],1,maxn,1,1);
dfs(v,dep+1);
update(len[e],1,maxn,1,-1);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&ch);
addedge(x,y,ch);
addedge(y,x,ch);
}
for (i=1;i<=n;i++){
memset(flag,0,sizeof flag);
dfs(i,0);
}
printf("%.7lf\n",(double)ans1/ans2);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,m,i,j,sum,q,opt,x,y,ans,edgenum,cnt,mx,tot;
int A[M],B[M],b[M],root[M],f[M],id[M],fi[M];
int head[1010],edg[1010],vet[M],next[M],len[M],isok[M],data[M];
struct shit{int x,y,w;}a[M];
struct node{int l,r,w;}tree[M*40];
bool cmp(shit x,shit y){return x.w>y.w;}
void addedge(int x,int y,int ch,int w){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
len[edgenum]=ch;
data[edgenum]=w;
}
int dfs(int u,int pre,int st){
int e,v;
if (u==st&&pre!=-1)return 1;
for (e=head[u];e;e=next[e]){
v=vet[e];
if (e==(pre^1))continue;
if (dfs(v,e,st)){
if (len[e]>len[mx])mx=e;
return 1;
}
}
return 0;
}
int search(int x){
if (f[x]!=x)f[x]=search(f[x]);
return f[x];
}
void update(int x,int l,int r,int &p,int t){
tree[++cnt]=tree[p],p=cnt,tree[p].w+=t;
if (l==r)return;
int mid=l+r>>1;
if (x<=mid)update(x,l,mid,tree[p].l,t);
else update(x,mid+1,r,tree[p].r,t);
}
int query(int x,int y,int l,int r,int p){
if (x>y)return 0;
if (x==l&&y==r)return tree[p].w;
int mid=l+r>>1;
if (y<=mid)return query(x,y,l,mid,tree[p].l);
else if (x>mid)return query(x,y,mid+1,r,tree[p].r);
else return query(x,mid,l,mid,tree[p].l)+query(mid+1,y,mid+1,r,tree[p].r);
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
int mm=0;
for (i=1;i<=m;i++)if (a[i].x!=a[i].y)a[++mm]=a[i];
m=mm;
sort(a+1,a+m+1,cmp);
for (i=1;i<=m;i++)A[i]=a[m-i+1].w;
sum=unique(A+1,A+m+1)-A-1;
for (i=1;i<=m;i++)id[i]=lower_bound(A+1,A+sum+1,a[i].w)-A;
for (i=1;i<=m;i++)id[i]=sum-id[i]+1;
for (i=1;i<=n;i++)f[i]=i;
for (i=1;i<=m;i++){
edgenum=1;
memset(head,0,sizeof head);
for (j=1;j<=edg[0];j++)addedge(a[edg[j]].x,a[edg[j]].y,a[edg[j]].w,edg[j]),addedge(a[edg[j]].y,a[edg[j]].x,a[edg[j]].w,edg[j]);
root[i]=root[i-1];
fi[id[i]]=i;
edg[++edg[0]]=i;
addedge(a[i].x,a[i].y,a[i].w,i);
addedge(a[i].y,a[i].x,a[i].w,i);
update(id[i],1,sum,root[i],a[i].w);
int p=search(a[i].x),q=search(a[i].y);
if (p!=q){
f[p]=q;
continue;
}
mx=0;
dfs(a[i].x,-1,a[i].x);
mx=data[mx];
update(id[mx],1,sum,root[i],-a[mx].w);
int mm=0;
for (j=1;j<=edg[0];j++)if (edg[j]!=mx)edg[++mm]=edg[j];
edg[0]=mm;
}
scanf("%d%d",&q,&opt);
while (q--){
scanf("%d%d",&x,&y);
int l=ans*opt+x,r=l+y,pre=r;
if (l>A[sum]){puts("0");ans=0;continue;}
l=lower_bound(A+1,A+sum+1,l)-A;
r=upper_bound(A+1,A+sum+1,r)-A-1;
r=sum-r+1,l=sum-l+1;
ans=query(r,l,1,sum,root[fi[l]]);
printf("%d\n",ans);
}
}
