whsstory

whsstory
7小时前
/**********/
#define MAXN 50011
struct Segment_Tree
{
ll t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
ll Qsum(un ql,un qr,un l=1,un r=MAXN-1,un num=1)
{
if(ql<=l&&r<=qr)return rt;
un mid=(l+r)>>1;ll ans=0;
if(ql<=mid)ans+=Qsum(ql,qr,l,mid,num<<1);
if(qr>mid)ans+=Qsum(ql,qr,mid+1,r,num<<1|1);
return ans;
}
void modify(un pos,ll k,un l=1,un r=MAXN-1,un num=1)
{
if(l==r){rt+=k;return;}
un mid=(l+r)>>1;
if(pos<=mid)modify(pos,k,l,mid,num<<1);
else modify(pos,k,mid+1,r,num<<1|1);
rt=tl+tr;
}
ll Qkth(ll k,un l=1,un r=MAXN-1,un num=1)//Query k-th 0
{
if(l==r)return l;
un mid=(l+r)>>1;
ll fl=mid-l+1-tl;
if(k<=fl)return Qkth(k,l,mid,num<<1);
else return Qkth(k-fl,mid+1,r,num<<1|1);
}
}sgt;
struct Seg
{
ll l,r,c;
bool operator <(const Seg& t)const{return r<t.r;}
}a[MAXN];
int main()
{
std::sort(a+1,a+n+1);
for(ll i=1;i<=n;++i)
{
ll k=a[i].c-sgt.Qsum(a[i].l,a[i].r);
if(k<0)continue;
ans+=k;
while(k--)
{
ll pos=sgt.Qkth(a[i].r-sgt.Qsum(1,a[i].r));
sgt.modify(pos,1);
}
}
printf("%lld",ans);
return 0;
}

whsstory
7小时前

//告别时间复杂度玄学的判负环,从我做起

/**********/
#define MAXN 50011
struct Segment_Tree
{
ll t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
ll Qsum(un ql,un qr,un l=1,un r=MAXN-1,un num=1)
{
if(ql<=l&&r<=qr)return rt;
un mid=(l+r)>>1;ll ans=0;
if(ql<=mid)ans+=Qsum(ql,qr,l,mid,num<<1);
if(qr>mid)ans+=Qsum(ql,qr,mid+1,r,num<<1|1);
return ans;
}
void modify(un pos,ll k,un l=1,un r=MAXN-1,un num=1)
{
if(l==r){rt+=k;return;}
un mid=(l+r)>>1;
if(pos<=mid)modify(pos,k,l,mid,num<<1);
else modify(pos,k,mid+1,r,num<<1|1);
rt=tl+tr;
}
ll Qkth(ll k,un l=1,un r=MAXN-1,un num=1)//Query k-th 0
{
if(l==r)return l;
un mid=(l+r)>>1;
ll fl=mid-l+1-tl;
if(k<=fl)return Qkth(k,l,mid,num<<1);
else return Qkth(k-fl,mid+1,r,num<<1|1);
}
}sgt;
struct Seg
{
ll l,r,c;
bool operator <(const Seg& t)const{return r<t.r;}
}a[MAXN];
int main()
{
std::sort(a+1,a+n+1);
for(ll i=1;i<=n;++i)
{
ll k=a[i].c-sgt.Qsum(a[i].l,a[i].r);
if(k<0)continue;
ans+=k;
while(k--)
{
ll pos=sgt.Qkth(a[i].r-sgt.Qsum(1,a[i].r));
sgt.modify(pos,1);
}
}
printf("%lld",ans);
return 0;
}

whsstory
8小时前
//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
/**********/
#define MAXN 50011
#define MAXM 2000011
ll n,m;
struct Graph
{
struct edge
{
ll v,nxt;
double w;
}e[MAXM];
ll cnt=0,last[MAXN];
{
e[++cnt].v=v,e[cnt].w=w;
e[cnt].nxt=last[u],last[u]=cnt;
}
void clear()
{
cnt=0;
for(ll i=1;i<=n;++i)last[i]=0;
}
}e,te;
ll val[MAXN],q[MAXN<<5|1],len[MAXN];
double dis[MAXN];
bool check(double k)
{
e.clear();
for(ll u=1;u<=n;++u)
for(ll i=te.last[u];i;i=te.e[i].nxt)
ll h=1,t=1;
for(ll i=1;i<=n;++i)dis[i]=1e15,len[i]=0;
dis[1]=0,q[t++]=1;
len[1]=1;
while(h<t)
{
ll u=q[h++];
for(ll i=e.last[u];i;i=e.e[i].nxt)
{
ll v=e.e[i].v;
if(dis[v]>dis[u]+e.e[i].w)len[v]=len[u]+1, dis[v]=dis[u]+e.e[i].w,q[t++]=v;
if(len[v]>n)return 1;
}
}
return 0;
}
int main()
{
for(ll i=1;i<=m;++i)
{
}
double l=-1e6,r=1e6;
while(r-l>0.001)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2f",l);
return 0;
}

whsstory
23小时前
//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
/**********/
#define MAXN 100011
ll a[MAXN],b[MAXN],n,k;
double p[MAXN];
bool check(double x)
{
for(ll i=1;i<=n;++i)p[i]=a[i]-x*b[i];
std::sort(p+1,p+n+1);
double sum=0;
for(ll i=n;i>k;--i)sum+=p[i];
return sum>=0;
}
int main()
{
{
double l=0,r=1e9;
while(r-l>1e-5)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.0f\n",l*100);
}
return 0;
}

whsstory
23小时前
//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const ll INF=1ll<<58;
/**********/
ll exgcd(ll a,ll b,ll& x,ll& y)
{
if(!b){x=1,y=0;return a;}
else
{
ll t=exgcd(b,a%b,y,x);
y-=a/b*x;
return t;
}
}
ll upd(ll x,ll p){return (x%p+p)%p;}
ll solve(ll a,ll b,ll mod)
{
ll x,y;
ll g=exgcd(a,mod,x,y);
x=upd(x,mod/g);
if(b%g)return -1ll;
return upd(x*b/g,mod/g);
}
int main()
{
ll a=m-n,b=sy-sx;
if(a<0)a=-a,b=-b;
ll ans=solve(a,b,L);
if(ans==-1)puts("Impossible");
else printf("%lld",ans);
return 0;
}

//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const ll INF=1ll<<58;
/**********/
#define MAXN 300011
struct one
{
ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
ll t[MAXN];
#define lowb (i&-i)
void modify(ll i,ll k)
{
while(i<=m)
{
t[i]+=k;
i+=lowb;
}
}
ll Qsum(ll i)
{
ll res=0;
while(i)
{
res+=t[i];
i-=lowb;
}
return res;
}
}t;

void solve(ll l,ll r,ll begin,ll end)
{
if(begin>end)return;
if(l==r)
{
for(ll i=begin;i<=end;++i)
ans[a[i]]=l;
return;
}
ll mid=(l+r)>>1;
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
}
ll itl=0,itr=0;
for(ll i=begin;i<=end;++i)
{
ll cnt=0;
for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
{
cnt+=t.Qsum(*it);
if(cnt>=need[a[i]])break;
}
if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
else la[++itl]=a[i];
}
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
}
for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
//freopen("data.in","r",stdin);
stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
solve(1,k+1,1,n);
for(ll i=1;i<=n;++i)
if(ans[i]>k)puts("NIE");
else printf("%lld\n",ans[i]);
return 0;
}

/**********/
#define MAXN 300011
struct one
{
ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
ll t[MAXN];
#define lowb (i&-i)
void modify(ll i,ll k)
{
while(i<=m)
{
t[i]+=k;
i+=lowb;
}
}
ll Qsum(ll i)
{
ll res=0;
while(i)
{
res+=t[i];
i-=lowb;
}
return res;
}
}t;

void solve(ll l,ll r,ll begin,ll end)
{
if(begin>end)return;
if(l==r)
{
for(ll i=begin;i<=end;++i)
ans[a[i]]=l;
return;
}
ll mid=(l+r)>>1;
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
}
ll itl=0,itr=0;
for(ll i=begin;i<=end;++i)
{
ll cnt=0;
for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
{
cnt+=t.Qsum(*it);
if(cnt>=need[a[i]])break;
}
if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
else la[++itl]=a[i];
}
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
}
for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
//freopen("data.in","r",stdin);
stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
solve(1,k+1,1,n);
for(ll i=1;i<=n;++i)
if(ans[i]>k)puts("NIE");
else printf("%lld\n",ans[i]);
return 0;
}

//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef long long ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const ll INF=1ll<<58;
/**********/
#define MAXN 300011
struct one
{
ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
ll t[MAXN];
#define lowb (i&-i)
void modify(ll i,ll k)
{
while(i<=m)
{
t[i]+=k;
i+=lowb;
}
}
ll Qsum(ll i)
{
ll res=0;
while(i)
{
res+=t[i];
i-=lowb;
}
return res;
}
}t;

void solve(ll l,ll r,ll begin,ll end)
{
if(begin>end)return;
if(l==r)
{
for(ll i=begin;i<=end;++i)
ans[a[i]]=l;
return;
}
ll mid=(l+r)>>1;
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
}
ll itl=0,itr=0;
for(ll i=begin;i<=end;++i)
{
ll cnt=0;
for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
{
cnt+=t.Qsum(*it);
if(cnt>=need[a[i]])break;
}
if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
else la[++itl]=a[i];
}
for(ll i=l;i<=mid;++i)
{
ll val=stone[i].val;
if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
}
for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
//freopen("data.in","r",stdin);
stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
solve(1,k+1,1,n);
for(ll i=1;i<=n;++i)
if(ans[i]>k)puts("NIE");
else printf("%lld\n",ans[i]);
return 0;
}

PS:询问容斥后查询的两个前缀应分配不同的时间戳,为了正确统计贡献为这些时间戳记录一下是第几个操作即可(代码中的num[])

/**********/
#define MAXN 200011
#define MAXW 2000011
struct Query
{
ll x,y1,y2,k,dex;
bool operator <(const Query& t)const
{
if(x==t.x)return y2<t.y2;
return x<t.x;
}
}a[MAXN];
struct BIT
{
ll t[MAXW];
#define lowb (i&-i)
void modify(ll i,ll k)
{
while(i<MAXW)t[i]+=k,i+=lowb;
}
ll Qsum(ll i)
{
ll res=0;
while(i)res+=t[i],i-=lowb;
return res;
}
}t;
ll ans[MAXN],is_query[MAXN],num[MAXN];
void CDQ(un l,un r)
{
if(l==r)return;
un mid=(l+r)>>1;
CDQ(l,mid),CDQ(mid+1,r);
std::sort(a+l,a+r+1);
for(ll i=l;i<=r;++i)
if(!a[i].y2)
{
if(a[i].dex<=mid)t.modify(a[i].y1,a[i].k);
}
else
{
if(a[i].dex>mid)ans[num[a[i].dex]]+=(t.Qsum(a[i].y2)-t.Qsum(a[i].y1))*a[i].k;
}
for(ll i=l;i<=r;++i)
if(!a[i].y2&&a[i].dex<=mid)t.modify(a[i].y1,-a[i].k);
}
int main()
{
{
++dex;
if(op==1)
{
a[++all]={x,y,0,k,all};
}
else
{
is_query[dex]=1;
a[++all]={x1-1,y1-1,y2,-1,all};num[all]=dex;
a[++all]={x2,y1-1,y2,1,all};num[all]=dex;
}
}
CDQ(1,all);
for(ll i=1;i<=dex;++i)
if(is_query[i])printf("%d\n",ans[i]);
return 0;
}

//Wan Hong 3.1
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
typedef int ll;
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
bool umax(ll& a,ll b){if(b>a)return a=b,1;return 0;}
bool umin(ll& a,ll b){if(b<a)return a=b,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
/**********/
#define MAXN 200011
#define MAXW 2000011
struct Query
{
ll x,y1,y2,k,dex;
bool operator <(const Query& t)const
{
if(x==t.x)return y2<t.y2;
return x<t.x;
}
}a[MAXN];
struct BIT
{
ll t[MAXW];
#define lowb (i&-i)
void modify(ll i,ll k)
{
while(i<MAXW)t[i]+=k,i+=lowb;
}
ll Qsum(ll i)
{
ll res=0;
while(i)res+=t[i],i-=lowb;
return res;
}
}t;
ll ans[MAXN],is_query[MAXN],num[MAXN];
void CDQ(un l,un r)
{
if(l==r)return;
un mid=(l+r)>>1;
CDQ(l,mid),CDQ(mid+1,r);
std::sort(a+l,a+r+1);
for(ll i=l;i<=r;++i)
if(!a[i].y2)
{
if(a[i].dex<=mid)t.modify(a[i].y1,a[i].k);
}
else
{
if(a[i].dex>mid)ans[num[a[i].dex]]+=(t.Qsum(a[i].y2)-t.Qsum(a[i].y1))*a[i].k;
}
for(ll i=l;i<=r;++i)
if(!a[i].y2&&a[i].dex<=mid)t.modify(a[i].y1,-a[i].k);
}
int main()
{
{
++dex;
if(op==1)
{
a[++all]={x,y,0,k,all};
}
else
{
is_query[dex]=1;