apple

陈柏诚  •  8天前


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;
}

Comments: