陈柏诚 • 1年前
3
3
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (k<<1)
#define rson ((k<<1)+1)
#define mid ((l+r)>>1)
const ll mod=1e9+7;
ll n,m,T,ind[200010],ans[800040];
inline void BuildTree(ll k,ll l,ll r)
{
if(l==r)
{
ans[k]=ind[l]%mod;
return ;
}
BuildTree(lson,l,mid),BuildTree(rson,mid+1,r),ans[k]=ans[lson]*ans[rson]%mod;
}
void Update(ll k,ll l,ll r,ll pos)
{
if(l>pos||r<pos) return ;
if(l==r)
{
ans[k]=(ans[k]+1)%mod;
return ;
}
Update(lson,l,mid,pos),Update(rson,mid+1,r,pos),ans[k]=ans[lson]*ans[rson]%mod;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&T);
for(ll i=1,x,y; i<=m; i++) scanf("%lld%lld",&x,&y),++ind[y];
ind[1]=1ll;
BuildTree(1,1,n);
printf("%lld\n",ans[1]);
for(ll i=1,x,y; i<=T; i++) scanf("%lld%lld",&x,&y),Update(1,1,n,y),printf("%lld\n",ans[1]);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (k<<1)
#define rson ((k<<1)+1)
#define mid ((l+r)>>1)
const ll mod=1e9+7;
ll n,m,T,ind[200010],ans[800040];
inline void BuildTree(ll k,ll l,ll r)
{
if(l==r)
{
ans[k]=ind[l]%mod;
return ;
}
BuildTree(lson,l,mid),BuildTree(rson,mid+1,r),ans[k]=ans[lson]*ans[rson]%mod;
}
void Update(ll k,ll l,ll r,ll pos)
{
if(l>pos||r<pos) return ;
if(l==r)
{
ans[k]=(ans[k]+1)%mod;
return ;
}
Update(lson,l,mid,pos),Update(rson,mid+1,r,pos),ans[k]=ans[lson]*ans[rson]%mod;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&T);
for(ll i=1,x,y; i<=m; i++) scanf("%lld%lld",&x,&y),++ind[y];
ind[1]=1ll;
BuildTree(1,1,n);
printf("%lld\n",ans[1]);
for(ll i=1,x,y; i<=T; i++) scanf("%lld%lld",&x,&y),Update(1,1,n,y),printf("%lld\n",ans[1]);
return 0;
}
评论: