Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
48332 呵呵 【AB-1】图 C++ 通过 100 119 MS 5848 KB 1079 2022-04-11 22:58:54

Tests(10/10):


#include <bits/stdc++.h> using namespace std; typedef long long ll ; const ll mod=1e9+7; ll n,m,T,a[200010],ans[800040]; inline void BuildTree(ll k,ll l,ll r) { ll lson=k*2; ll rson=k*2+1; ll mid=(l+r)/2; if(l==r) { ans[k]=a[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) { ll lson=k*2; ll rson=k*2+1; ll mid=(l+r)/2; //ll lson=k<<1;不知为何一用位运算就会出问题 // ll rson=k<<1|1; // ll mid=(l+r)>>2; 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); a[y]++; } a[1]=1; 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; }


测评信息: