题目大意：给你一个长度为n的数组a，然后数值大的可以合并数值小的，且合并了以后该数组的长度-1.给你一个长度为k目标数组b，问，是否可以从a数组变到b数组，是就yes并且输出步骤。否就输出no
思路：因为合并的时候要删除某一个数字，很容易想到用树状数组来维护。然后分析一下就可以得到b中第i个数，一定是由a的某一段区间得到的。我们只要找到这一段区间就行啦。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #pragma comment(linker,"/STACK:102400000,102400000") 4 #define LL long long 5 #define ALL(a) a.begin(), a.end() 6 #define pb push_back 7 #define mk make_pair 8 #define fi first 9 #define se second 10 #define haha printf("haha ") 11 const int maxn = 500 + 5; 12 int n, k; 13 int a[maxn], b[maxn]; 14 int tree[maxn]; 15 vector<pair<int, int> > v; 16 17 void update(int x, int val = 1){ 18 for (int i = x; i <= maxn - 5; i += i & -i) 19 tree[i] += val; 20 } 21 22 int sum(int pos){ 23 int ans = 0; 24 for (int i = pos - 1; i > 0; i -= i & -i){ 25 ans += tree[i]; 26 } 27 return ans; 28 } 29 30 vector<pair<int, char> > ans; 31 32 void eat(int pos, int lb, int rb){ 33 if (pos == rb || a[pos] > a[pos - 1]){ 34 for (int i = pos - 1; i >= lb; i--){ 35 int reduce = sum(pos); 36 ans.push_back(mk(pos - reduce, 'L')); 37 update(i); 38 } 39 for (int i = pos + 1; i <= rb; i++){ 40 int reduce = sum(pos); 41 ans.push_back(mk(pos - reduce, 'R')); 42 update(i); 43 } 44 } 45 else { 46 for (int i = pos + 1; i <= rb; i++){ 47 int reduce = sum(pos); 48 ans.push_back(mk(pos - reduce, 'R')); 49 update(i); 50 } 51 for (int i = pos - 1; i >= lb; i--){ 52 int reduce = sum(pos); 53 ans.push_back(mk(pos - reduce, 'L')); 54 update(i); 55 } 56 } 57 } 58 59 bool solve(){ 60 a[n + 1] = 0x3f3f3f3f; 61 int lb = 1; 62 for (int i = 1; i <= k; i++){ 63 int val = b[i]; 64 for (int j = lb; j <= n; j++){ 65 if (val == a[j]){ 66 v.push_back(mk(lb, j)); 67 lb = j + 1; 68 break; 69 } 70 else if (val > a[j]) val -= a[j]; 71 else return false; 72 } 73 if (lb > n) break; 74 } 75 if (v.size() != k) return false; 76 for (int i = 0; i < v.size(); i++){ 77 int lb = v[i].fi, rb = v[i].se; 78 int val = a[lb]; 79 bool flag = (rb == lb ? true : false); 80 for (int j = lb + 1; j <= rb; j++){ 81 if (val != a[j]) { 82 flag = true; 83 break; 84 } 85 } 86 if (!flag) return false; 87 } 88 for (int i = 0; i < v.size(); i++){ 89 int lb = v[i].fi, rb = v[i].se; 90 if (lb == rb) continue; 91 int maxval = a[lb], pos = lb; 92 for (int j = lb + 1; j <= rb; j++){ 93 if (maxval < a[j]) {maxval = a[j]; pos = j;} 94 else if (maxval == a[j] && a[j - 1] < a[j]) pos = j; 95 else if (maxval == a[j] && a[j + 1] < a[j] && j < rb) pos = j; 96 } 97 eat(pos, lb, rb); 98 } 99 return true; 100 } 101 102 int main(){ 103 scanf("%d", &n); 104 int sum = 0; 105 for (int i = 1; i <= n; i++) scanf("%d", a + i), sum += a[i]; 106 scanf("%d", &k); 107 for (int i = 1; i <= k; i++) scanf("%d", b + i), sum -= b[i]; 108 if (sum != 0) printf("NO "); 109 else { 110 bool flag = solve(); 111 if (!flag) printf("NO "); 112 else { 113 printf("YES "); 114 for (int i = 0; i < ans.size(); i++){ 115 pair<int, char> p = ans[i]; 116 printf("%d %c ", p.fi, p.se); 117 } 118 } 119 } 120 return 0; 121 }