牛客周赛 Round 57

B

可以直接统计每条边两个点的情况即可，不用DFS。

F

写法和这个差不多。可以用map、set、统计这些方法，计算动态的一个数组的最大数。

可以直接用map统计就行，map已经自动给你排好序了（从小到大）。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define LL long long
  4 #define ULL unsigned long long
  5 
  6 const LL mod_1=1e9+7;
  7 const LL mod_2=998244353;
  8 
  9 const double eps_1=1e-5;
 10 const double eps_2=1e-10;
 11 
 12 const int maxn=1e5+10;
 13 
 14 vector<int> vec[maxn];
 15 map<int,int> mp[maxn];
 16 set<int> st[maxn];
 17 int value[maxn*2], single_min[maxn];
 18 
 19 void build(int index, int l, int r)
 20 {
 21     if (l==r)
 22         value[index] = single_min[l];
 23     else
 24     {
 25         int mid = (l+r)/2;
 26         build(index*2,l,mid);
 27         build(index*2+1,mid+1,r);
 28 
 29         value[index] = min(value[index*2],value[index*2+1]);
 30     }
 31 }
 32 
 33 void modify(int index, int l, int r, int k)
 34 {
 35     if (l==r)
 36         value[index] = single_min[k];
 37     else
 38     {
 39         int mid = (l+r)/2;
 40         if (l<=k && k<=mid)
 41             modify(index*2,l,mid,k);
 42         if (mid+1<=k && k<=r)
 43             modify(index*2+1,mid+1,r,k);
 44 
 45         value[index] = min(value[index*2],value[index*2+1]);
 46     }
 47 }
 48 
 49 int getv(int index, int l, int r, int k)
 50 {
 51     if (r<=k)
 52         return value[index];
 53     else
 54     {
 55         int mid = (l+r)/2, result=INT_MAX;
 56         if (l<=k)
 57             result = min( result, getv(index*2,l,mid,k) );
 58         if (mid+1<=k)
 59             result = min( result, getv(index*2+1,mid+1,r,k) );
 60         return result;
 61     }
 62 }
 63 
 64 int main()
 65 {
 66     int n,m,i,j,k,q,t,x,x_old;
 67     scanf("%d",&n);
 68     for (i=1;i<=n;i++)
 69     {
 70         scanf("%d",&m);
 71         for (j=1;j<=m;j++)
 72         {
 73             scanf("%d",&k);
 74             vec[i].push_back(k);
 75             mp[i][k]++;
 76             st[i].insert(k);
 77         }
 78         single_min[i] = *st[i].begin();
 79     }
 80 
 81     build(1,1,n);
 82     
 83     scanf("%d",&q);
 84     while (q--)
 85     {
 86         scanf("%d",&t);
 87         if (t==1)
 88         {
 89             scanf("%d%d%d",&i,&j,&x);
 90             x_old=vec[i][j-1];
 91             if (mp[i][x_old]==1)
 92                 st[i].erase(x_old);
 93             mp[i][x_old]--;
 94             vec[i][j-1]=x;
 95             if (!mp[i][x])
 96                 st[i].insert(x);
 97             mp[i][x]++;
 98 
 99             single_min[i] = *st[i].begin();
100             modify(1,1,n,i);
101         }
102         else
103         {
104             scanf("%d",&i);
105             printf("%d\n",getv(1,1,n,i));
106         }
107     }
108 
109     return 0;
110 }