GTMD这么水的一套题没有AK
T1：妥妥的二分答案，贪心check。
T2：问题可以转化为最长上升（还是下降我记不住了）子序列。
T3：发现点被覆盖上的顺序是一定的。求出这个顺序，第一个操作在线段树上二分，第二个操作是找到这个点最上面那个有人的点，把他的状态变为没人。
P.S.常数这么大也能过。。。
然而一开始260为什么呢。。
anc开的maxv*20还TMfor到了20。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxn 100500
#define eps 1e-6
#define inf 0x7f7f7f7f7f7f7f7fLL
using namespace std;
long long n,h,x;
double l=,r=,ans;
vector <long long> v[maxn];
bool check(double x)
{
double ret=;
for (long long i=;i<=n;i++)
{
double mx=-inf;
for (long long j=;j<=h;j++)
mx=max(mx,(double)v[i][j]-x*j);
ret+=mx;
}
if (ret>=) return true;
return false;
}
int main()
{
scanf("%lld%lld",&n,&h);
for (long long i=;i<=n;i++)
{
v[i].push_back();
for (long long j=;j<=h;j++)
{
scanf("%lld",&x);
v[i].push_back(v[i][j-]+x);
}
}
while (r-l>=eps)
{
double mid=(l+r)/;
if (check(mid)) {ans=l=mid;}
else r=mid;
}
printf("%.4lf\n",ans);
return ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100500
using namespace std;
int n,a[maxn],b[maxn],x,t[maxn],ans=,ret=;
int lowbit(int x) {return (x&(-x));}
void modify(int x,int val)
{
for (int i=x;i<=n;i+=lowbit(i))
t[i]=max(t[i],val);
}
int ask(int x)
{
int ret=;
for (int i=x;i>=;i-=lowbit(i))
ret=max(ret,t[i]);
return ret;
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<=n;i++)
{
scanf("%d",&x);
b[x]=i;
}
for (int i=;i<=n;i++)
{
ret=ask(n-b[a[i]]+);
ans=max(ans,ret+);
modify(n-b[a[i]]+,ret+);
}
printf("%d\n",ans);
return ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define maxv 100500
using namespace std;
int n,m,x,y,g[maxv],nume=,op,dfn[maxv],fdfn[maxv],times=,dis[maxv],anc[maxv][];
int root,tot=,ls[maxv<<],rs[maxv<<],sum[maxv<<],lazy[maxv<<];
vector <int> v[maxv];
void dfs(int x,int fath)
{
for (int i=;i<v[x].size();i++)
{
int pos=v[x][i];
if (pos==fath) continue;
anc[pos][]=x;dis[pos]=dis[x]+;
dfs(pos,x);
}
dfn[x]=++times;fdfn[times]=x;
}
void get_table()
{
for (int i=;i<=;i++)
for (int j=;j<=n;j++)
anc[j][i]=anc[anc[j][i-]][i-];
}
void build(int &now,int left,int right)
{
now=++tot;sum[now]=right-left+;lazy[now]=;
if (left==right) return;
int mid=left+right>>;
build(ls[now],left,mid);
build(rs[now],mid+,right);
}
void pushdown(int now)
{
if (!lazy[now]) return;
lazy[ls[now]]=lazy[rs[now]]=lazy[now];
sum[ls[now]]=sum[rs[now]]=;lazy[now]=;
}
void pushup(int now)
{
sum[now]=sum[ls[now]]+sum[rs[now]];
}
int ask1(int now,int left,int right,int x)
{
pushdown(now);
if (left==right) return left;
int mid=left+right>>,k=sum[ls[now]];
if (x<=k) return ask1(ls[now],left,mid,x);
else return ask1(rs[now],mid+,right,x-k);
}
void modify1(int now,int left,int right,int l,int r)
{
if ((left==l) && (right==r))
{
lazy[now]=;sum[now]=;
return;
}
int mid=left+right>>;
if (r<=mid) modify1(ls[now],left,mid,l,r);
else if (l>=mid+) modify1(rs[now],mid+,right,l,r);
else
{
modify1(ls[now],left,mid,l,mid);
modify1(rs[now],mid+,right,mid+,r);
}
pushup(now);
}
int ask2(int now,int left,int right,int pos)
{
pushdown(now);
if (left==right) return sum[now];
int mid=left+right>>;
if (pos<=mid) return ask2(ls[now],left,mid,pos);
else return ask2(rs[now],mid+,right,pos);
}
void modify2(int now,int left,int right,int pos)
{
pushdown(now);
if (left==right) {sum[now]=;return;}
int mid=left+right>>;
if (pos<=mid) modify2(ls[now],left,mid,pos);
else modify2(rs[now],mid+,right,pos);
pushup(now);
}
void work1()
{
int pos=ask1(root,,n,x);
printf("%d\n",fdfn[pos]);
modify1(root,,n,,pos);
}
void work2()
{
int ret=x;
for (int i=;i>=;i--)
{
if (!anc[ret][i]) continue;
if (!ask2(root,,n,dfn[anc[ret][i]])) ret=anc[ret][i];
}
printf("%d\n",dis[x]-dis[ret]);
modify2(root,,n,dfn[ret]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n-;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);v[y].push_back(x);
}
for (int i=;i<=n;i++) sort(v[i].begin(),v[i].end());
dfs(,);get_table();
build(root,,n);
for (int i=;i<=m;i++)
{
scanf("%d%d",&op,&x);
if (op==) work1();
else work2();
}
return ;
}