题目

题目链接-BZOJ4552

题目大意似乎和题目描述差不多，略。。。

题解

简单（精妙）而慢的解法

对某个区间排序。

这种操作如果选一个数，将比它小的数当成0，比它大的数当成1。

那么，就变成了对区间覆盖0或1的问题。

所以我们可以来二分答案。

若将小于等于x的全赋成0，大于x的全赋成1。

那么就是求最小的x，使询问的位置经过若干操作后等于0。

快叫好！！！

“吼啊！”

时间复杂度

二分 $O(lgn)$

判定 $O(mlgn)$

总时间复杂度 $O(mlg^2n)$

代码

#include <cstdio>

int n, m;
int x[200000];
int tmp[200000];
int sum[1000000], tag[1000000];
int cas[200000], l[200000], r[200000];
int pos;

void pushup(int k)
{
    sum[k] = sum[k << 1] + sum[k << 1 | 1];
}

void pushdown(int k, int l, int r)
{
    if (tag[k] != -1)
    {
        int mid = l + r >> 1;
        tag[k << 1] = tag[k];
        sum[k << 1] = tag[k] * (mid - l + 1);
        tag[k << 1 | 1] = tag[k];
        sum[k << 1 | 1] = tag[k] * (r - mid);
        tag[k] = -1;
    }
}

void build(int k, int l, int r)
{
    if (l == r)
    {
        sum[k] = tmp[l];
        tag[k] = -1;
        return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
    tag[k] = -1;
}

void change(int k, int l, int r, int L, int R, int newvalue)
{
    if (L <= l && r <= R)
    {
        tag[k] = newvalue;
        sum[k] = newvalue * (r - l + 1);
        return;
    }
    pushdown(k, l, r);
    int mid = l + r >> 1;
    if (L <= mid)
    {
        change(k << 1, l, mid, L, R, newvalue);
    }
    if (R > mid)
    {
        change(k << 1 | 1, mid + 1, r, L, R, newvalue);
    }
    pushup(k);
}

int query(int k, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
    {
        return sum[k];
    }
    pushdown(k, l, r);
    int ans = 0;
    int mid = l + r >> 1;
    if (L <= mid)
    {
        ans += query(k << 1, l, mid, L, R);
    }
    if (R > mid)
    {
        ans += query(k << 1 | 1, mid + 1, r, L, R);
    }
    return ans;
}

bool check(int mid)
{
    for (int i = 1; i <= n; i++)
    {
        tmp[i] = x[i] > mid;
    }
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        if (cas[i] == 0)
        {
            int cnt1 = query(1, 1, n, l[i], r[i]);
            int cnt0 = r[i] - l[i] + 1 - cnt1;
            if (cnt0 > 0)
            {
                change(1, 1, n, l[i], l[i] + cnt0 - 1, 0);
            }
            if (cnt1 > 0)
            {
                change(1, 1, n, l[i] + cnt0, r[i], 1);
            }
        }
        else
        {
            int cnt1 = query(1, 1, n, l[i], r[i]);
            int cnt0 = r[i] - l[i] + 1 - cnt1;
            if (cnt1 > 0)
            {
                change(1, 1, n, l[i], l[i] + cnt1 - 1, 1);
            }
            if (cnt0 > 0)
            {
                change(1, 1, n, l[i] + cnt1, r[i], 0);
            }
        }
    }
    return query(1, 1, n, pos, pos) == 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &cas[i], &l[i], &r[i]);
    }
    scanf("%d", &pos);
    int ll = 1;
    int rr = n;
    while (ll < rr)
    {
        int mid = ll + rr >> 1;
        if (check(mid))
        {
            rr = mid;
        }
        else
        {
            ll = mid + 1;
        }
    }
    printf("%d\n", ll);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

#include <cstdio>

int n, m;

int x[200000];

int tmp[200000];

int sum[1000000], tag[1000000];

int cas[200000], l[200000], r[200000];

int pos;

void pushup(int k)

{

sum[k] = sum[k << 1] + sum[k << 1 | 1];

}

void pushdown(int k, int l, int r)

{

if (tag[k] != -1)

{

int mid = l + r >> 1;

tag[k << 1] = tag[k];

sum[k << 1] = tag[k] * (mid - l + 1);

tag[k << 1 | 1] = tag[k];

sum[k << 1 | 1] = tag[k] * (r - mid);

tag[k] = -1;

}

void build(int k, int l, int r)

{

if (l == r)

{

sum[k] = tmp[l];

tag[k] = -1;

return;

}

int mid = l + r >> 1;

build(k << 1, l, mid);

build(k << 1 | 1, mid + 1, r);

pushup(k);

tag[k] = -1;

}

void change(int k, int l, int r, int L, int R, int newvalue)

{

if (L <= l && r <= R)

{

tag[k] = newvalue;

sum[k] = newvalue * (r - l + 1);

return;

}

pushdown(k, l, r);

int mid = l + r >> 1;

if (L <= mid)

{

change(k << 1, l, mid, L, R, newvalue);

}

if (R > mid)

{

change(k << 1 | 1, mid + 1, r, L, R, newvalue);

}

pushup(k);

}

int query(int k, int l, int r, int L, int R)

{

if (L <= l && r <= R)

{

return sum[k];

}

pushdown(k, l, r);

int ans = 0;

int mid = l + r >> 1;

if (L <= mid)

{

ans += query(k << 1, l, mid, L, R);

}

if (R > mid)

{

ans += query(k << 1 | 1, mid + 1, r, L, R);

}

return ans;

}

bool check(int mid)

{

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

{

tmp[i] = x[i] > mid;

}

build(1, 1, n);

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

{

if (cas[i] == 0)

{

int cnt1 = query(1, 1, n, l[i], r[i]);

int cnt0 = r[i] - l[i] + 1 - cnt1;

if (cnt0 > 0)

{

change(1, 1, n, l[i], l[i] + cnt0 - 1, 0);

}

if (cnt1 > 0)

{

change(1, 1, n, l[i] + cnt0, r[i], 1);

}

else

{

int cnt1 = query(1, 1, n, l[i], r[i]);

int cnt0 = r[i] - l[i] + 1 - cnt1;

if (cnt1 > 0)

{

change(1, 1, n, l[i], l[i] + cnt1 - 1, 1);

}

if (cnt0 > 0)

{

change(1, 1, n, l[i] + cnt1, r[i], 0);

}

return query(1, 1, n, pos, pos) == 0;

}

int main()

{

scanf("%d%d", &n, &m);

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

{

scanf("%d", &x[i]);

}

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

{

scanf("%d%d%d", &cas[i], &l[i], &r[i]);

}

scanf("%d", &pos);

int ll = 1;

int rr = n;

while (ll < rr)

{

int mid = ll + rr >> 1;

if (check(mid))

{

rr = mid;

}

else

{

ll = mid + 1;

}

printf("%d\n", ll);

return 0;

}

快而复杂（吐血）的解法

这种做法可以处理多个询问，还可以在线做。

那么是什么呢？

没错，模拟大法好！

。。。

开始第i个位置都表示区间$ [i,i] $，弄一棵动态开点的权值线段树，并且权值线段树里记录下i位置的值。

然后每棵线段树还有个rev表示是从大到小还是从小到大。

然后就可以模拟啦。

外面弄一棵线段树维护每个位置在哪个区间中。

然后修改操作就是找一段包含修改区间的连续的区间，头尾两个区间可能是部分包含的，所以还要用到线段树的split操作（雾），然后就是线段树的merge了。介绍线段树的合并与分裂的传送门。

这段代码居然让我码了一个多小时。。。

时间复杂度

每次操作最多split两次，所以main函数里最多split $O(n + m)$ 次，并且线段树节点数最多 $O((n + m)lgn)$ 个，所以最后的时间复杂度为 $O((n + m)lgn)$

代码

#include <cstdio>
#include <algorithm>

int n, m;
int root[200000], rev[200000];
int tag[1000000];
int num;
int ch[10000000][2], sum[10000000];

void pushup(int k)
{
    if (k)
    {
        sum[k] = sum[ch[k][0]] + sum[ch[k][1]];
    }
}

void change(int &u, int l, int r, int pos, int delta)
{
    num++;
    u = num;
    sum[u] = delta;
    if (l == r)
    {
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
    {
        change(ch[u][0], l, mid, pos, delta);
    }
    else
    {
        change(ch[u][1], mid + 1, r, pos, delta);
    }
}

int query(int k, int l, int r, int rank)
{
    if (l == r)
    {
        return l;
    }
    int mid = l + r >> 1;
    if (rank <= sum[ch[k][0]])
    {
        return query(ch[k][0], l, mid, rank);
    }
    else
    {
        return query(ch[k][1], mid + 1, r, rank - sum[ch[k][0]]);
    }
}

std::pair<int, int> split(int x, int rank)
{
    if (! x)
    {
        return std::make_pair(0, 0);
    }
    if (rank <= sum[ch[x][0]])
    {
        std::pair<int, int> tmp = split(ch[x][0], rank);
        num++;
        ch[num][0] = tmp.first;
        ch[x][0] = tmp.second;
        sum[num] = rank;
        sum[x] = sum[x] - rank;
        return std::make_pair(num, x);
    }
    else
    {
        std::pair<int, int> tmp = split(ch[x][1], rank - sum[ch[x][0]]);
        num++;
        ch[num][1] = tmp.second;
        ch[x][1] = tmp.first;
        sum[num] = sum[x] - rank;
        sum[x] = rank;
        return std::make_pair(x, num);
    }
}

std::pair<int, int> split(int x, int rank, int cas)
{
    std::pair<int, int> ans;
    if (cas)
    {
        ans = split(x, sum[x] - rank);
        std::swap(ans.first, ans.second);
        return ans;
    }
    else
    {
        ans = split(x, rank);
        return ans;
    }
}

void merge(int &x, int y)
{
    if (! y)
    {
        return;
    }
    if (! x)
    {
        x = y;
        return;
    }
    sum[x] += sum[y];
    merge(ch[x][0], ch[y][0]);
    merge(ch[x][1], ch[y][1]);
}

void pushdownbelong(int k)
{
    if (tag[k])
    {
        tag[k << 1] = tag[k << 1 | 1] = tag[k];
        tag[k] = 0;
    }
}

void buildbelong(int k, int l, int r)
{
    tag[k] = 0;
    if (l == r)
    {
        tag[k] = l;
        return;
    }
    int mid = l + r >> 1;
    buildbelong(k << 1, l, mid);
    buildbelong(k << 1 | 1, mid + 1, r);
}

void changebelong(int k, int l, int r, int L, int R, int newvalue)
{
    if (L <= l && r <= R)
    {
        tag[k] = newvalue;
        return;
    }
    pushdownbelong(k);
    int mid = l + r >> 1;
    if (L <= mid)
    {
        changebelong(k << 1, l, mid, L, R, newvalue);
    }
    if (R > mid)
    {
        changebelong(k << 1 | 1, mid + 1, r, L, R, newvalue);
    }
}

int querybelong(int k, int l, int r, int pos)
{
    if (l == r)
    {
        return tag[k];
    }
    pushdownbelong(k);
    int mid = l + r >> 1;
    if (pos <= mid)
    {
        return querybelong(k << 1, l, mid, pos);
    }
    else
    {
        return querybelong(k << 1 | 1, mid + 1, r, pos);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        change(root[i], 1, n, x, 1);
        rev[i] = 0;
    }
    buildbelong(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int cas, l, r;
        scanf("%d%d%d", &cas, &l, &r);
        int ll = querybelong(1, 1, n, l);
        int rr = querybelong(1, 1, n, r);
        if (ll == rr)
        {
            std::pair<int, int> x1, x2;
            int v = rev[ll];
            x1 = split(root[ll], l - ll, v);
            x2 = split(x1.second, r - l + 1, v);
            if (sum[x1.first])
            {
                root[ll] = x1.first;
                rev[ll] = v;
                changebelong(1, 1, n, ll, ll + sum[x1.first] - 1, ll);
            }
            if (sum[x2.first])
            {
                root[l] = x2.first;
                rev[l] = cas;
                changebelong(1, 1, n, l, l + sum[x2.first] - 1, l);
            }
            if (sum[x2.second])
            {
                root[r + 1] = x2.second;
                rev[r + 1] = v;
                changebelong(1, 1, n, r + 1, r + 1 + sum[x2.second] - 1, r + 1);
            }
        }
        else
        {
            int now = 0;
            for (int j = ll + sum[root[ll]]; j != rr; j = j + sum[root[j]])
            {
                merge(now, root[j]);
            }
            int v;
            std::pair<int, int> tmp;
            v = rev[ll];
            tmp = split(root[ll], l - ll, v);
            if (sum[tmp.first])
            {
                root[ll] = tmp.first;
                rev[ll] = v;
                changebelong(1, 1, n, ll, ll + sum[tmp.first] - 1, ll);
            }
            merge(now, tmp.second);
            v = rev[rr];
            tmp = split(root[rr], r - rr + 1, v);
            if (sum[tmp.second])
            {
                root[r + 1] = tmp.second;
                rev[r + 1] = v;
                changebelong(1, 1, n, r + 1, r + 1 + sum[tmp.second] - 1, r + 1);
            }
            merge(now, tmp.first);
            root[l] = now;
            rev[l] = cas;
            changebelong(1, 1, n, l, r, l);
        }
    }
    int pos;
    scanf("%d", &pos);
    int kk = querybelong(1, 1, n, pos);
    if (rev[kk])
    {
        printf("%d\n", query(root[kk], 1, n, sum[root[kk]] - (pos - kk + 1) + 1));
    }
    else
    {
        printf("%d\n", query(root[kk], 1, n, pos - kk + 1));
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

#include <cstdio>

#include <algorithm>

int n, m;

int root[200000], rev[200000];

int tag[1000000];

int num;

int ch[10000000][2], sum[10000000];

void pushup(int k)

{

if (k)

{

sum[k] = sum[ch[k][0]] + sum[ch[k][1]];

}

void change(int &u, int l, int r, int pos, int delta)

{

num++;

u = num;

sum[u] = delta;

if (l == r)

{

return;

}

int mid = l + r >> 1;

if (pos <= mid)

{

change(ch[u][0], l, mid, pos, delta);

}

else

{

change(ch[u][1], mid + 1, r, pos, delta);

}

int query(int k, int l, int r, int rank)

{

if (l == r)

{

return l;

}

int mid = l + r >> 1;

if (rank <= sum[ch[k][0]])

{

return query(ch[k][0], l, mid, rank);

}

else

{

return query(ch[k][1], mid + 1, r, rank - sum[ch[k][0]]);

}

std::pair<int, int> split(int x, int rank)

{

if (! x)

{

return std::make_pair(0, 0);

}

if (rank <= sum[ch[x][0]])

{

std::pair<int, int> tmp = split(ch[x][0], rank);

num++;

ch[num][0] = tmp.first;

ch[x][0] = tmp.second;

sum[num] = rank;

sum[x] = sum[x] - rank;

return std::make_pair(num, x);

}

else

{

std::pair<int, int> tmp = split(ch[x][1], rank - sum[ch[x][0]]);

num++;

ch[num][1] = tmp.second;

ch[x][1] = tmp.first;

sum[num] = sum[x] - rank;

sum[x] = rank;

return std::make_pair(x, num);

}

std::pair<int, int> split(int x, int rank, int cas)

{

std::pair<int, int> ans;

if (cas)

{

ans = split(x, sum[x] - rank);

std::swap(ans.first, ans.second);

return ans;

}

else

{

ans = split(x, rank);

return ans;

}

void merge(int &x, int y)

{

if (! y)

{

return;

}

if (! x)

{

x = y;

return;

}

sum[x] += sum[y];

merge(ch[x][0], ch[y][0]);

merge(ch[x][1], ch[y][1]);

}

void pushdownbelong(int k)

{

if (tag[k])

{

tag[k << 1] = tag[k << 1 | 1] = tag[k];

tag[k] = 0;

}

void buildbelong(int k, int l, int r)

{

tag[k] = 0;

if (l == r)

{

tag[k] = l;

return;

}

int mid = l + r >> 1;

buildbelong(k << 1, l, mid);

buildbelong(k << 1 | 1, mid + 1, r);

}

void changebelong(int k, int l, int r, int L, int R, int newvalue)

{

if (L <= l && r <= R)

{

tag[k] = newvalue;

return;

}

pushdownbelong(k);

int mid = l + r >> 1;

if (L <= mid)

{

changebelong(k << 1, l, mid, L, R, newvalue);

}

if (R > mid)

{

changebelong(k << 1 | 1, mid + 1, r, L, R, newvalue);

}

int querybelong(int k, int l, int r, int pos)

{

if (l == r)

{

return tag[k];

}

pushdownbelong(k);

int mid = l + r >> 1;

if (pos <= mid)

{

return querybelong(k << 1, l, mid, pos);

}

else

{

return querybelong(k << 1 | 1, mid + 1, r, pos);

}

int main()

{

scanf("%d%d", &n, &m);

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

{

int x;

scanf("%d", &x);

change(root[i], 1, n, x, 1);

rev[i] = 0;

}

buildbelong(1, 1, n);

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

{

int cas, l, r;

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

int ll = querybelong(1, 1, n, l);

int rr = querybelong(1, 1, n, r);

if (ll == rr)

{

std::pair<int, int> x1, x2;

int v = rev[ll];

x1 = split(root[ll], l - ll, v);

x2 = split(x1.second, r - l + 1, v);

if (sum[x1.first])

{

root[ll] = x1.first;

rev[ll] = v;

changebelong(1, 1, n, ll, ll + sum[x1.first] - 1, ll);

}

if (sum[x2.first])

{

root[l] = x2.first;

rev[l] = cas;

changebelong(1, 1, n, l, l + sum[x2.first] - 1, l);

}

if (sum[x2.second])

{

root[r + 1] = x2.second;

rev[r + 1] = v;

changebelong(1, 1, n, r + 1, r + 1 + sum[x2.second] - 1, r + 1);

}

else

{

int now = 0;

for (int j = ll + sum[root[ll]]; j != rr; j = j + sum[root[j]])

{

merge(now, root[j]);

}

int v;

std::pair<int, int> tmp;

v = rev[ll];

tmp = split(root[ll], l - ll, v);

if (sum[tmp.first])

{

root[ll] = tmp.first;

rev[ll] = v;

changebelong(1, 1, n, ll, ll + sum[tmp.first] - 1, ll);

}

merge(now, tmp.second);

v = rev[rr];

tmp = split(root[rr], r - rr + 1, v);

if (sum[tmp.second])

{

root[r + 1] = tmp.second;

rev[r + 1] = v;

changebelong(1, 1, n, r + 1, r + 1 + sum[tmp.second] - 1, r + 1);

}

merge(now, tmp.first);

root[l] = now;

rev[l] = cas;

changebelong(1, 1, n, l, r, l);

}

int pos;

scanf("%d", &pos);

int kk = querybelong(1, 1, n, pos);

if (rev[kk])

{

printf("%d\n", query(root[kk], 1, n, sum[root[kk]] - (pos - kk + 1) + 1));

}

else

{

printf("%d\n", query(root[kk], 1, n, pos - kk + 1));

}

return 0;

}

PhoenixGS

一道题的简单（精妙）而慢和快而复杂（吐血）的解法

题目

题解

简单（精妙）而慢的解法

时间复杂度

代码

快而复杂（吐血）的解法

时间复杂度

代码

2 thoughts on “一道题的简单（精妙）而慢和快而复杂（吐血）的解法”

向chengbowei进行回复取消回复

题目

题解

简单（精妙）而慢的解法

时间复杂度

代码

快而复杂（吐血）的解法

时间复杂度

代码

2 thoughts on “一道题的简单（精妙）而慢和快而复杂（吐血）的解法”

向chengbowei进行回复 取消回复

向chengbowei进行回复取消回复