[BZOJ2883]gss2加强版

其实这题跟GSS2毛线关系都没有,求的根本不一样么,这题求的就是区间和,GSS2那题求的是区间和的最大值……但是相同的是:都是每个数只算一次

其实看到这题我的想法就是线段树套动态分配的权值线段树,外层的线段树用来限制区间,顺便维护区间和,内层的权值线段树记下每个数出现的次数,这样修改的时候只要对每个数次数次数由0变1或者由1变0进行特判,更新区间和即可。然后就很高兴的去打了,结果连样例都过不去,才发现这样还是有BUG:在外层线段树查询的时候,左右子树的并还是可能有重复的数……后来YY了一下,干脆query就构造一棵内层的线段树,时间复杂度看起来不会很糟糕,但是事实证明空间复杂度相当高(后来下了数据,发现时间复杂度也非常高),所以这是一种非常不可行的方法。

后来请教了下ygy副队,发现对于这种一个数只记一次的题目有一种通用的方法:一维转二维。我们把a[i]转成一个二维点:(last[i], i)last[i]i之前a[i]出现的位置,呃,因为这题要求和嘛,所以我们可以给这个二维点一个值a[i],这样我们就完美的把一维的数转成了二维的点。

接下来查询区间[L, R]就十分愉悦了,直接查找x[0, L-1]并且y[L, R]的所有点的和。

然后就是修改了,考虑一下修改一个数会改变多少个点,修改相当于去掉一个数,再添上一个数。对于去掉一个数a[i],显然会影响到a[i]相邻两个和他相同的数。所以去掉一个数会影响3个点,所以一次修改操作会影响6个点。为了方便的维护一个数和他相同数的位置,可以维护一棵平衡树。

实际写起来还是很好写的,内存也不是很大。

bzoj2883gss2加强版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>
using std::set;
using std::vector;

const int MAXN = 100001;
const int MEMORYSIZE = 1024*1024*4;
//------1D SegmentTree
struct Segment1D
{
  long long sum;
  Segment1D *lef, *rig;
} _memory[MEMORYSIZE], *_memory_top = _memory;
int n, _n;
class SegmentTree1D
{
#define CREATE_AND_GO(func, node, ...) { if (!node) node = _memory_top++; func(node, __VA_ARGS__); }
  Segment1D *root;
  long long query(Segment1D* const node, const int lef, const int rig, const int st, const int ed)
  {
    if (!node->sum) return 0;
    if (st <= lef && rig <= ed) return node->sum;
    const int mid = (lef+rig)/2;
    long long sum = 0;
    if (st <= mid && node->lef) sum += query(node->lef, lef, mid, st, ed);
    if (mid+1 <= ed && node->rig) sum += query(node->rig, mid+1, rig, st, ed);
    return sum;
  }
  void modify(Segment1D* const node, const int lef, const int rig, const int pos, const int delta)
  {
    node->sum += delta;
    if (lef == rig) return;
    const int mid = (lef+rig)/2;
    if (pos <= mid) CREATE_AND_GO(modify, node->lef, lef, mid, pos, delta)
    else CREATE_AND_GO(modify, node->rig, mid+1, rig, pos, delta)
  }
#undef CREATE_AND_GO
public:
  long long Query(const int lef, const int rig) { return query(root, 1, n, lef, rig); }
  void Modify(const int pos, const int delta) { modify(root, 1, n, pos, delta); }
  SegmentTree1D(): root(_memory_top++) { }
};
//------2D BIT
SegmentTree1D C[MAXN*2];
inline void Modify(const int x, const int y, const int delta)
{
  for (int i = x+1; i <= _n; i += i&-i)
    C[i].Modify(y, delta);
}
inline long long Query(const int x, const int y1, const int y2)
{
  long long res = 0;
  for (int i = x+1; i; i -= i&-i)
    res += C[i].Query(y1, y2);
  return res;
}
//------Main Program
int m, a[MAXN], x[MAXN], y[MAXN];
char o[MAXN];
set<int> sets[MAXN*2];
int main()
{
  scanf("%d", &n);
  vector<int> v;
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", a+i);
    v.push_back(a[i]);
  }
  scanf("%d", &m);
  for (int i = 0; i < m; ++i)
  {
    scanf("\n%c%d%d", o+i, x+i, y+i);
    if (o[i] == 'U') v.push_back(y[i]);
  }
  std::sort(v.begin(), v.end());
  v.resize(std::unique(v.begin(), v.end())-v.begin());
  _n = n+1;

  for (size_t i = 0; i < v.size(); ++i) sets[i].insert(0);
  for (int i = 1; i <= n; ++i)
  {
    const int cur = std::lower_bound(v.begin(), v.end(), a[i])-v.begin();
    const int last = *sets[cur].rbegin();
    Modify(last, i, +a[i]);
    sets[cur].insert(i);
  }
  for (int i = 0; i < m; ++i)
  {
    if (o[i] == 'Q')
      printf("%lld\n", Query(x[i]-1, x[i], y[i]));
    else
    {
      const int pos = x[i], value = y[i];

      const int pre = std::lower_bound(v.begin(), v.end(), a[pos])-v.begin();
      set<int>::iterator target = sets[pre].find(pos), succ, prev;
      Modify(*--(prev = target), pos, -a[pos]);
      if (++(succ = target) != sets[pre].end())
      {
        Modify(pos, *succ, -a[pos]);
        Modify(*prev, *succ, +a[pos]);
      }
      sets[pre].erase(target);

      const int cur = std::lower_bound(v.begin(), v.end(), value)-v.begin();
      sets[cur].insert(pos);
      target = sets[cur].find(pos);
      Modify(*--(prev = target), pos, +value);
      if (++(succ = target) != sets[cur].end())
      {
        Modify(*prev, *succ, -value);
        Modify(pos, *succ, +value);
      }

      a[pos] = value;
    }
  }
  //printf("\n\n%10d\n%10d\n%.6fMBytes\n", _memory_top-_memory, MEMORYSIZE, (sizeof(_memory)+sizeof(x)+sizeof(y)+sizeof(o)+sizeof(C))/1024.0/1024.0);
}

Comments