5k_sync_closer @ 2023-01-31 22:06:26
查询中建的临时节点要及时回收，指针被卡常就换数组，还过不了就开小点
by 5k_sync_closer @ 2023-01-31 22:06:45
（TLE 30 可能的解决方法）
by lyhqwq @ 2023-01-31 22:24:03
@5k_sync_closer 5k爷教我数据结构吧/bx/bx/bx
by NaN_HQJ2007_NaN @ 2023-02-02 20:58:46
@lyhqwq 你先把黄题做明白吧hhhhhh
by lyhqwq @ 2023-02-02 21:17:44
@EstasTonne 是这样的（悲
by weijia33 @ 2023-07-07 17:59:38
@5k_sync_closer 5k大佬具体的怎么回收，代码如下
// Problem: P2839 [国家集训队] middle
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2839
// Memory Limit: 512 MB
// Time Limit: 2000 ms
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
inline int read();
#define mid (l + r >> 1)
#define lson l , mid
#define rson mid + 1 , r
#define N N << 4
int ls[N] , rs[N] , tot;
struct node
{
int lmax , rmax , sum;
}t[N];
node hb (node a , node b)
{
node tmp;
tmp.lmax = max(a.lmax , a.sum + b.lmax);
tmp.rmax = max(b.rmax , b.sum + a.rmax);
tmp.sum = a.sum + b.sum;
return tmp;
}
void pushup (int rt){t[rt] = hb(t[ls[rt]] , t[rs[rt]]);}
void build (int &rt , int l , int r)
{
rt = ++tot;
if (l == r) return t[rt] = {1 , 1 , 1}, void();
build(ls[rt] , lson);
build(rs[rt] , rson);
pushup(rt);
}
void upd (int &rt , int l , int r , int p , int k)
{
rt = ++tot;
ls[rt] = ls[p]; rs[rt] = rs[p];
if (l == r) return t[rt] = {-1 , -1 , -1} , void();
if (k <= mid) upd(ls[rt] , lson , ls[p] , k);
else upd(rs[rt] , rson , rs[p] , k);
pushup(rt);
}
node query (int rt , int l , int r , int ll , int rr)
{
if (ll > rr) return {0 , 0 , 0};
if (ll <= l && r <= rr) return t[rt];
if (rr <= mid) return query(ls[rt] , lson , ll , rr);
if (ll > mid) return query(rs[rt] , rson , ll , rr);
return hb(query(ls[rt] , lson , ll , rr) , query(rs[rt] , rson , ll , rr));
}
#undef N
int cnt , a[N] , f[N] , lst = 0 , root[N] , q[5];
void work (int a , int b , int c , int d)
{
int l = 1 , r = cnt , ans = 0;
while (l <= r)
{
node tmp1 = query(root[mid] , 1 , cnt , a , b)
, tmp2 = query(root[mid] , 1 , cnt , c , d)
, tmp3 = query(root[mid] , 1 , cnt , b + 1 , c - 1);
if (tmp1.rmax + tmp2.lmax + tmp3.sum >= 0) ans = mid , l = mid + 1;
else r = mid - 1;
}
cout << (lst = f[ans]) << "\n";
}
struct weijia
{
int v , ip;
bool operator < (const weijia a) const
{
return v < a.v;
}
}b[N];
int main()
{
int n = read();
for (int i = 1 ; i <= n ; i++) f[i] = a[i] = read();
sort(f + 1 , f + 1 + n);
cnt = unique(f + 1 , f + 1 + n) - f - 1;
for (int i = 1 ; i <= n ; i++)
b[i] = {lower_bound(f + 1 , f + 1 + n , a[i]) - f , i};
sort(b + 1 , b + 1 + n);
build(root[1] , 1 , cnt);
for (int i = 2 ; i <= n ; i++)
{
if (b[i].v == b[i - 1].v) root[b[i].v] = root[b[i].v];
else upd(root[b[i].v] , 1 , cnt , root[b[i - 1].v] , b[i - 1].ip);
}
int m = read();
for (; m ; --m)
{
int a = read() , b = read() , c = read() ,d = read();
q[1] = (a + lst) % n , q[2] = (b + lst) % n , q[3] = (c + lst) % n , q[4] = (d + lst) % n;
sort (q + 1 , q + 5);
work(q[1] + 1, q[2] + 1, q[3] + 1, q[4] + 1);
}
return 0;
}
inline int read ()
{
int x = 0 , y = 1; char ch = getchar ();
while (ch < '0' || ch > '9') {if(ch == '-')y = -1 ; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - 48 ; ch = getchar();}
return x * y;
}by weijia33 @ 2023-07-07 18:11:55
emm 找到好几处错，不T了 开始WA了
// Problem: P2839 [国家集训队] middle
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2839
// Memory Limit: 512 MB
// Time Limit: 2000 ms
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
inline int read();
#define mid (l + r >> 1)
#define lson l , mid
#define rson mid + 1 , r
#define N N << 4
int ls[N] , rs[N] , tot;
struct node
{
int lmax , rmax , sum;
}t[N];
node hb (node a , node b)
{
node tmp;
tmp.lmax = max(a.lmax , a.sum + b.lmax);
tmp.rmax = max(b.rmax , b.sum + a.rmax);
tmp.sum = a.sum + b.sum;
return tmp;
}
void pushup (int rt){t[rt] = hb(t[ls[rt]] , t[rs[rt]]);}
void build (int &rt , int l , int r)
{
rt = ++tot;
if (l == r) return t[rt] = {1 , 1 , 1}, void();
build(ls[rt] , lson);
build(rs[rt] , rson);
pushup(rt);
}
void upd (int &rt , int l , int r , int p , int k)
{
rt = ++tot;
ls[rt] = ls[p]; rs[rt] = rs[p];
if (l == r) return t[rt] = {-1 , -1 , -1} , void();
if (k <= mid) upd(ls[rt] , lson , ls[p] , k);
else upd(rs[rt] , rson , rs[p] , k);
pushup(rt);
}
node query (int rt , int l , int r , int ll , int rr)
{
if (ll > rr) return {0 , 0 , 0};
if (ll <= l && r <= rr) return t[rt];
if (rr <= mid) return query(ls[rt] , lson , ll , rr);
if (ll > mid) return query(rs[rt] , rson , ll , rr);
return hb(query(ls[rt] , lson , ll , rr) , query(rs[rt] , rson , ll , rr));
}
#undef N
int cnt , a[N] , f[N] , lst = 0 , root[N] , q[5] , n;
void work (int a , int b , int c , int d)
{
int l = 1 , r = cnt , ans = 0;
while (l <= r)
{
node tmp1 = query(root[mid] , 1 , n , a , b)
, tmp2 = query(root[mid] , 1 , n , c , d)
, tmp3 = query(root[mid] , 1 , n , b + 1 , c - 1);
if (tmp1.rmax + tmp2.lmax + tmp3.sum >= 0) ans = mid , l = mid + 1;
else r = mid - 1;
}
cout << (lst = f[ans]) << "\n";
}
struct weijia
{
int v , ip;
bool operator < (const weijia a) const
{
return v < a.v;
}
}b[N];
int main()
{
n = read();
for (int i = 1 ; i <= n ; i++) f[i] = a[i] = read();
sort(f + 1 , f + 1 + n);
cnt = unique(f + 1 , f + 1 + n) - f - 1;
for (int i = 1 ; i <= n ; i++)
b[i] = {lower_bound(f + 1 , f + 1 + cnt , a[i]) - f , i};
sort(b + 1 , b + 1 + n);
build(root[1] , 1 , n);
for (int i = 2 ; i <= n ; i++)
{
if (b[i].v == b[i - 1].v) root[b[i].v] = root[b[i - 1].v];
else upd(root[b[i].v] , 1 , n , root[b[i - 1].v] , b[i - 1].ip);
}
int m = read();
for (; m ; --m)
{
int a = read() , b = read() , c = read() ,d = read();
q[1] = (a + lst) % n , q[2] = (b + lst) % n , q[3] = (c + lst) % n , q[4] = (d + lst) % n;
sort (q + 1 , q + 5);
work(q[1] + 1, q[2] + 1, q[3] + 1, q[4] + 1);
}
return 0;
}
inline int read ()
{
int x = 0 , y = 1; char ch = getchar ();
while (ch < '0' || ch > '9') {if(ch == '-')y = -1 ; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - 48 ; ch = getchar();}
return x * y;
}by weijia33 @ 2023-07-07 19:05:59
AC 了，但不理解：
build(root[1] , 1 , n);
for (int i = 2 ; i <= n ; i++)
upd(root[i] , 1 , n , root[i-1] , a[i - 1].ip);当建树时有 a[i].v == a[i - 1].v 的情况时，我们仍然在 i - 1 的版本上把1修改为 -1，而我们是将>=的改为-1，并且重合时所有重合的节点的版本不一样 这么建不会出锅吗