关于这道题最后一个点

DPair @ 2021-05-03 07:33:43

by DPair @ 2021-05-03 07:34:05

//翻涌的银河，在此化作怒涛之光展现身姿吧！
#include <assert.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i,s,t) for(int i=(s);i<=(t);++i)
#define per(i,t,s) for(int i=(t);i>=(s);--i)
#define REP(i,s,t) for(int i=(s);i<(t);++i)
#define PER(i,t,s) for(int i=(t);i>(s);--i)
#define elif else if
const double pi = 3.141592653589793238462643383279;
namespace MyMinMax{
template <typename T>
inline T mn(const T x, const T y) {return x < y ? x : y;}
template <typename T>
inline T mx(const T x, const T y) {return x > y ? x : y;}
template <typename T>
inline bool chmin(T &x, const T y) {return (x > y) && ((x = y), 1);}
template <typename T>
inline bool chmax(T &x, const T y) {return (x < y) && ((x = y), 1);}
template <typename T, typename ...Args>
inline T mx(const T x, const Args ...args) {return mx(x, mx(args...));}
template <typename T, typename ...Args>
inline T mn(const T x, const Args ...args) {return mn(x, mn(args...));}
}
using namespace MyMinMax;
namespace IO{
const int DPAIRSIZ = 1 << 18;
char BB[DPAIRSIZ], *SS = BB, *TT = BB;
inline char getcha(){return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS ++;}
template <typename T = int>
inline T read(){
    T x = 0;int fu = 1;
    char c = getcha();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getcha();
    }
    while(c <= 57 && c >= 48){
        x = x * 10 + c - 48;
        c = getcha();
    }
    x *= fu;return x;
}
template <typename T>
inline void read(T &x){
    x = 0;int fu = 1;
    char c = getcha();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getcha();
    }
    while(c <= 57 && c >= 48){
        x = x * 10 + c - 48;
        c = getcha();
    }
    x *= fu;
}
template <typename T>
inline void read(T *bg, T *ed){while(bg != ed) read(*bg ++);}
inline void read(char &ch){
    ch = getcha();
    while(ch <= 32) ch = getcha();
}
inline void read(char *s){
    char ch = getcha();
    while(ch <= 32) ch = getcha();
    while(ch > 32) *s ++ = ch, ch = getcha();
    *s = '\0';
}
inline void sread(char *s){
    char ch = getcha();
    while(ch < 32) ch = getcha();
    while(ch >= 32) *s ++ = ch, ch = getcha();
    *s = '\0';
}
inline void pread(char *&s){
    char ch = getcha();
    while(ch <= 32) ch = getcha();
    while(ch > 32) *s ++ = ch, ch = getcha();
    *s = '\0';
}
inline void spread(char *&s){
    char ch = getcha();
    while(ch < 32) ch = getcha();
    while(ch >= 32) *s ++ = ch, ch = getcha();
    *s = '\0';
}
template <typename T, typename ...Args>
inline void read(T &x, Args &...args){read(x);read(args...);}
char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)
inline void putcha(char x) {*Out++ = x;if(Out - out >= (DPAIRSIZ)) flush(), Out = out;}
template <typename T>
inline void fprint(T x){
    if(x < 0) putcha(45), x = -x;
    if(x > 9) fprint(x / 10);
    putcha(x % 10 + 48);
}
inline void print(){putcha(10);}
template <typename T>
inline void print(T x){fprint(x);putcha(10);}
inline void print(char *ch){while(*ch != '\0') putcha(*(ch ++));putcha(10);}
inline void put(char *ch){while(*ch != '\0') putcha(*(ch ++));}
inline void print(const char *ch){while(*ch != '\0') putcha(*(ch ++));putcha(10);}
inline void put(const char *ch){while(*ch != '\0') putcha(*(ch ++));}
template <typename T, typename ...Args>
inline void print(T x, Args ...args){fprint(x);putcha(32);print(args...);}
template <typename ...Args>
inline void print(const char *ch, Args ...args){while(*ch != '\0') putcha(*(ch ++));putcha(32);print(args...);}
template <typename ...Args>
inline void print(char *ch, Args ...args){while(*ch != '\0') putcha(*(ch ++));putcha(32);print(args...);}
template <typename T, typename ...Args>
inline void printl(T x, Args ...args){fprint(x);putcha(10);printl(args...);}
template <typename ...Args>
inline void printl(const char *ch, Args ...args){while(*ch != '\0') putcha(*(ch ++));putcha(10);printl(args...);}
template <typename ...Args>
inline void printl(char *ch, Args ...args){while(*ch != '\0') putcha(*(ch ++));putcha(10);printl(args...);}
template <typename T>
inline void sprint(T x){fprint(x);putcha(32);}
template <typename T, typename ...Args>
inline void sprint(T x, Args ...args){fprint(x);putcha(32);sprint(args...);}
template <typename T>
inline void sprint(T *bg, T *ed){while(bg != ed) sprint(*bg ++);}
template <typename T>
inline void print(T *bg, T *ed){while(bg != ed) sprint(*bg ++);putcha(10);}
template <typename T>
inline void printl(T *bg, T *ed){while(bg != ed) print(*bg ++);}
class AutoFlush{
    public:
        ~AutoFlush(){flush();}
}__AutoFlush;
} // namespace IO
using namespace IO;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL INFll = 0x3f3f3f3f3f3f3f3fll;
/* My Code begins here */
const int MAXN = 5e4 + 5, block = 255, B = MAXN / block + 5;
int a[MAXN], P[B], bel[MAXN], n, m;
int f[B][block + 5], cur[35];
int pre[B][35], p[B], pp[MAXN];
int suf[B][35], s[B], ss[MAXN];
int t[B];
bool tag[B];
struct DPair{
    int id, val;
    DPair(int id = 0, int val = 0) : id(id), val(val) {}
}g[35], G[35];

int c1[16], c2[16];
inline void Sort() {
    REP(j, 0, 31) {
        ++ c1[g[j].val & 15];
        ++ c2[g[j].val >> 4];
    }
    rep(i, 1, 15) {
        c1[i] += c1[i - 1];
        c2[i] += c2[i - 1];
    }
    per(i, 30, 0) G[-- c1[g[i].val & 15]] = g[i];
    per(i, 30, 0) g[-- c2[G[i].val >> 4]] = G[i];
    memset(c1, 0, sizeof(c1));
    memset(c2, 0, sizeof(c2));
}

inline void rebuild(const int x) {
    const int l = P[x - 1] + 1, r = P[x];
    t[x] = 0; memset(f[x], 0, sizeof(f[x])); REP(i, 0, 31) cur[i] = block;
    per(i, r, l) { t[x] |= a[i]; REP(j, 0, 31) if(a[i] >> j & 1) cur[j] = i - l;
        REP(j, 0, 31) g[j] = DPair(j, cur[j]);
        Sort(); int val = 0; REP(j, 0, 31) {
            if(g[j].val == block) break;
            const int pos = g[j].val + l; 
            chmax(f[x][pos - i + 1], val |= (1 << g[j].id));
        }
    } rep(i, l, r) chmax(f[x][i - l + 1], f[x][i - l]);
    // 先处理出 f 数组，再处理前驱后继
    pp[l] = a[l]; ss[r] = a[r];
    pre[x][p[x] = 1] = l; suf[x][s[x] = 1] = r;
    rep(i, l + 1, r) if((pp[i] = pp[i - 1] | a[i]) != pp[i - 1]) pre[x][++ p[x]] = i;// 如果发生了改变
    per(i, r - 1, l) if((ss[i] = ss[i + 1] | a[i]) != ss[i + 1]) suf[x][++ s[x]] = i;// 如果发生了改变
}
inline int ask(const int k, const int x) {return k <= t[x]? (std :: lower_bound(f[x] + 1, f[x] + P[x] - P[x - 1] + 1, k) - f[x]) : INF; }
inline void init() {
    rep(i, 1, n) bel[i] = (i - 1) / block + 1;
    rep(i, 1, bel[n]) P[i] = mn(i * block, n);
    rep(i, 1, bel[n]) rebuild(i);
}
struct SGT{
    int tr[B << 2];
    inline void pushup(int rt){tr[rt] = tr[rt << 1] | tr[rt << 1 | 1];}
    void build(int rt, int l, int r) {
        if(l == r) return tr[rt] = t[l], void();
        int mid = (l + r) >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r);
        pushup(rt);
    }
    void ins(int rt, int l, int r, int x, int y) {
        if(l == r) return tr[rt] = y, void();
        int mid = (l + r) >> 1;
        x <= mid? ins(rt << 1, l, mid, x, y) : ins(rt << 1 | 1, mid + 1, r, x, y);
        pushup(rt);
    }
    int query(int rt, int l, int r, int x, int y) {
        if(x <= l && r <= y) return tr[rt];
        int mid = (l + r) >> 1;
        if(x > mid) return query(rt << 1 | 1, mid + 1, r, x, y);
        if(y <= mid) return query(rt << 1, l, mid, x, y);
        return query(rt << 1, l, mid, x, y) | query(rt << 1 | 1, mid + 1, r, x, y);
    }
}sgt;

inline int query(const int k) { if(!k) return 1;
    int ans = n; rep(i, 1, bel[n]) {
        if(tag[i]) { 
            rebuild(i); tag[i] = 0;
            sgt.ins(1, 1, bel[n], i, t[i]);
        } chmin(ans, ask(k, i));
    }
    if(sgt.tr[1] < k) return -1;
    int M = 0, R = 0, r = 0, it = 0; // 中间整块的 or 和
    REP(L, 1, bel[n]) {// 枚举左块
        M = 0; if(R <= L) R = L + 1, r = pre[R][it = 1];// 不能在同一块
        if(L + 1 <= R - 1) M = sgt.query(1, 1, bel[n], L + 1, R - 1);
        per(i, s[L], 1) { const int l = suf[L][i]; int S = ss[l] | M | pp[r];
            while(S < k) {
                while(it < p[R] && S < k) S |= pp[r = pre[R][++ it]];
                if(S < k) {
                    if(R == bel[n]) return ans;
                    S |= (M |= t[R]); S |= pp[r = pre[++ R][it = 1]]; 
                }
            } chmin(ans, r - l + 1);
        }
    } return ans;
}
int main() {
    read(n, m); read(a + 1, a + n + 1); init();
    sgt.build(1, 1, bel[n]); while(m --) {
        if(read() == 1) {int x; read(x); read(a[x]); tag[bel[x]] = 1;} 
        else print(query(read()));
    }
}

by FutaRimeWoawaSete @ 2021-05-03 08:31:17

你应该是剪枝加少了（

by FutaRimeWoawaSete @ 2021-05-03 08:32:09

@DPair 我之前也是剪枝加少，尽管我是贺的shadowice的代码

by DPair @ 2021-05-03 08:35:06

@FutaRimeWoawaSete 过了，应该是最优解

by FutaRimeWoawaSete @ 2021-05-03 08:41:26

@DPair 你在重构块的时候这么剪枝：来个变量记录一下前缀/后缀的或值，当前的前缀/后缀或值记为 sum ，记修改后的 a[pos] 的值为 x ,如果 sum == (sum & x)就说明当前这个修改的位置对后面/前面没有贡献了，我们后面/前面不需要重构了，直接剪枝。

by FutaRimeWoawaSete @ 2021-05-03 08:42:27

@DPair 那恭喜。

by FutaRimeWoawaSete @ 2021-05-03 08:43:20

果然就我一个人会被这种题卡常到贺代码

by DPair @ 2021-05-03 08:43:45

@FutaRimeWoawaSete

对哦，有道理

这就去把最优解卡得更离谱