[bzoj3351]Regions

Bertha 。 2021-11-17 15:34 204阅读 0赞

这道题有一种较为暴力的做法，对于每个点枚举所有与r2为该属性的询问并加以修改，最坏时间复杂度为o(nq)，然而是可过的(97s)

发现只有当r2相同的询问数特别多时才会达到最坏时间复杂度，因此如果删除重复询问，时间复杂度降为o(nr)，然而并没有显著优化(81s)

接着考虑当同一种r2的询问特别多时(大于K)，可以从r1考虑，分析一下时间复杂度发现是$o(n\\cdot max(K,R/K))\\ge o(n\\sqrt\{R\})$，即取$K=\\sqrt\{R\}$，此时只要13s

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 200005
     4 vector<int>v1[N],v2[N];
     5 struct ji{
     6     int nex,to;
     7 }edge[N];
     8 map<pair<int,int> ,int>mat;
     9 int E,n,m,q,x,y,sum[N],a[N],b[N],f[N],ans[N],tot[N],head[N];
    10 void add(int x,int y){
    11     edge[E].nex=head[x];
    12     edge[E].to=y;
    13     head[x]=E++;
    14 }
    15 void dfs(int k,int fa){
    16     tot[a[k]]++;
    17     for(int i=0;i<v2[a[k]].size();i++){
    18         x=v2[a[k]][i];
    19         ans[x]+=tot[b[x]];
    20     }
    21     for(int i=head[k];i!=-1;i=edge[i].nex)
    22         if (edge[i].to!=fa)dfs(edge[i].to,k);
    23     tot[a[k]]--;
    24 }
    25 void dfs2(int k,int fa){
    26     tot[a[k]]++;
    27     for(int i=0;i<v1[a[k]].size();i++){
    28         x=v1[a[k]][i];
    29         ans[x]-=tot[b[x]];
    30     }
    31     for(int i=head[k];i!=-1;i=edge[i].nex)
    32         if (edge[i].to!=fa)dfs2(edge[i].to,k);
    33     for(int i=0;i<v1[a[k]].size();i++){
    34         x=v1[a[k]][i];
    35         ans[x]+=tot[b[x]];
    36     }
    37 }
    38 int main(){
    39     scanf("%d%d%d",&n,&m,&q);
    40     memset(head,-1,sizeof(head));
    41     for(int i=1;i<=n;i++){
    42         if (i!=1){
    43             scanf("%d",&x);
    44             add(x,i);
    45         }
    46         scanf("%d",&a[i]);
    47         sum[a[i]]++;
    48     }
    49     for(int i=1;i<=q;i++){
    50         scanf("%d%d",&x,&y);
    51         if (mat[make_pair(x,y)])f[i]=mat[make_pair(x,y)];
    52         else{
    53             f[i]=mat[make_pair(x,y)]=i;
    54             if (sum[y]>500){
    55                 v1[x].push_back(i);
    56                 b[i]=y;
    57             }
    58             else{
    59                 v2[y].push_back(i);
    60                 b[i]=x;
    61             }
    62         }
    63     }
    64     dfs(1,0);
    65     dfs2(1,0);
    66     for(int i=1;i<=q;i++)printf("%d\n",ans[f[i]]);
    67 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11249797.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/8e0cfb08065346f7af9cf608dd67ca39.png