2018 Multi-University Training Contest 2 Solution

A - Absolute

留坑。

B - Counting Permutations

留坑。

C - Cover

留坑。

D - Game

puts("Yes")

 #include <bits/stdc++.h>

 using namespace std;

 int n;

 int main()

 {

     while (scanf("%d", &n) != EOF)

     {

         puts("Yes");

     }

     return ;

 }

E - Hack It

留坑。

F - Matrix

留坑。

G - Naive Operations

题意：给出$b[]$数组，里面是$1-n$ 的全排列，两种操作，一个区间+1，一个是区间求$\sum_{i = l} ^ {i = r} \lfloor \frac{a_i}{b_i} \rfloor$

思路：维护一个Min 表示这个区间内需要的最少的进位，如果有进位，就更新到底，如果没有进位就区间更新

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 #define ll long long

 ll arr[N];

 struct node

 {

     int l, r;

     ll Min, lazy, sum, v;

     inline node() {}

     inline node(int _l, int _r)

     {

         l = _l; r = _r;

         Min = , lazy = , sum = , v = ;

     }

 }tree[N << ];

 inline void pushup(int id)

 {

     tree[id].Min = min(tree[id << ].Min, tree[id <<  | ].Min);

     tree[id].sum = tree[id << ].sum + tree[id <<  | ].sum;

 }

 inline void pushdown(int id)

 {

     if(tree[id].l >= tree[id].r) return;

     if(tree[id].lazy)

     {

         tree[id << ].lazy += tree[id].lazy;

         tree[id <<  | ].lazy += tree[id].lazy;

         tree[id << ].Min -= tree[id].lazy;

         tree[id <<  | ].Min -= tree[id].lazy;

         tree[id].lazy = ;

     }

 }

 inline void build(int id, int l, int r)

 {

     tree[id] = node(l, r);

     if (l == r)

     {

         tree[id].v = arr[l];

         tree[id].Min = arr[l];

         return;

     }

     int mid = (l + r) >> ;

     build(id << , l, mid);

     build(id <<  | , mid + , r);

     pushup(id);

 }

 inline void update(int id, int l, int r)

 {

     if (tree[id].l == l && tree[id].r == r && tree[id].Min > )

     {

         tree[id].lazy++;

         tree[id].Min--;

         return ;

     }

     if(tree[id].l == tree[id].r && tree[id].Min == )

     {

         tree[id].Min = tree[id].v;

         tree[id].sum++;

         return ;

     }

     pushdown(id);

     int mid = (tree[id].l + tree[id].r) >> ;

     if (r <= mid) update(id << , l, r);

     else if (l > mid) update(id <<  | , l, r);

     else

     {

         update(id << , l, mid);

         update(id <<  | , mid + , r);

     }

     pushup(id);

 }

 ll anssum;

 inline void query(int id, int l, int r)

 {

     if (tree[id].l >= l && tree[id].r <= r)

     {

         anssum += tree[id].sum;

         return;

     }

     pushdown(id);

     int mid = (tree[id].l + tree[id].r) >> ;

     if (l <= mid) query(id << , l, r);

     if (r > mid) query(id <<  | , l, r);

     pushup(id);

 }

 int n, m;

 char str[];

 int l, r;

 int main()

 {

     while(~scanf("%d %d", &n, &m))

     {

         for(int i = ; i <= n; ++i) scanf("%lld", arr + i);

         build(, , n);

         for(int i = ; i <= m; ++i)

         {

             scanf("%s", str);

             if(str[] == 'a')

             {

                 scanf("%d %d", &l, &r);

                 update(, l, r);

             }

             else

             {

                 scanf("%d %d", &l, &r);

                 anssum = ;

                 query(, l, r);

                 printf("%lld\n", anssum);

             }

         }

     }

     return ;

 }

H - Odd Shops

留坑。

I - Segment

留坑。

J - Swaps and Inversions

水。逆序对的意义就是每次只能交换相邻两个，最少的交换次数

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define N 100010

 int n, m; ll x, y;

 int arr[N], brr[N];

 int a[N];

 inline void Init()

 {

     for (int i = ; i <= n; ++i) brr[i] = arr[i];

     sort(brr + , brr +  + n);

     m = unique(brr + , brr +  + n) - brr - ;

 }

 inline int Get(int x)

 {

     return lower_bound(brr + , brr +  + m, x) - brr;

 }

 inline int lowbit(int x)

 {

     return x & (-x);

 }

 inline void update(int x, int val)

 {

     for (int i = x; i <= n; i += lowbit(i))

         a[i] += val;

 }

 inline int query(int x)

 {

     int res = ;

     for (int i = x; i > ; i -= lowbit(i))

         res += a[i];

     return res;

 }

 int main()

 {

     while (scanf("%d%lld%lld", &n, &x, &y) != EOF)

     {

         for (int i = ; i <= n; ++i) scanf("%d", arr + i);

         Init(); memset(a, , sizeof a);

         for (int i = ; i <= n; ++i) arr[i] = Get(arr[i]);

         ll ans = ;

         for (int i = ; i <= n; ++i)

         {

         //    ans += i - 1 - query(arr[i] - 1);

         //    printf("%d %d\n", arr[i], query(arr[i] - 1));

             update(arr[i], );

             ans += i - query(arr[i]);

         //    cout << arr[i] << " " << query(arr[i]) << endl;

         }

         printf("%lld\n", min(ans * x, ans * y));

     }

     return ;

 }