锯锯锯锯锯锯锯锯锯锯锯锯锯锯
分析
牛客评测机挺快。这道题,千万不要无脑开1e8的数组(比如我),把所有的询问离线下来,以次数为关键字排一个序,然后就按顺序扫着走,记录答案即可
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
ll n,tot;
ll ans[N],cnt[N];
struct nkl
{
ll x,id;
}s[N<<2];
inline void add(ll i,ll x)
{
s[++tot].id=i;
s[tot].x=x;
}
inline bool god(nkl xx,nkl yy)
{
return xx.x<yy.x;
}
inline ll get(ll x,ll y)
{
ll ret=1;
for (;y;y>>=1,x=x*x%mod)
if(y&1) ret=ret*x%mod;
return ret;
}
int main()
{
scanf("%lld",&n);
for (ll i=1;i<=n;i++)
{
ll x,y;
scanf("%lld%lld",&x,&y);
add(i,x);add(i,y);
}sort(s+1,s+tot+1,god);
ll now=1,st=0;
for (ll i=1;i<=tot;i++)
{
while(st<s[i].x)
++st,now=(now*now+now)%mod;
if(!ans[s[i].id]) ans[s[i].id]=now;
else ans[s[i].id]=now*get(ans[s[i].id],mod-2)%mod;
}
for (ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
return 0;
}