本文共 4767 字，大约阅读时间需要 15 分钟。
刚开始看这个题目，觉得没法做。关键点是数据小于100。因此，可以枚举所有小于100的素因子进行位压缩。
1 /* 3071 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set 26 #define stpii set > 27 #define mpii map 28 #define vi vector 29 #define pii pair 30 #define vpii vector > 31 #define rep(i, a, n) for (int i=a;i =a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 #define ui32 unsigned int 43 44 typedef struct { 45 ui32 mx, mn; 46 } node_t; 47 48 int factor[25] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}; 49 int width[25] = { 3,3,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 50 int shift[25] = { 28,25,23,21,20,19,18,17,16,15,14,13,12,11,10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; 51 int mask[25] = { 7,7,3,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 52 const int maxn = 1e5+5; 53 int M[25][8]; 54 node_t nd[maxn<<2]; 55 int L, R, mod; 56 57 void init() { 58 rep(i, 0, 25) { 59 M[i][0] = 1; 60 rep(j, 1, mask[i]+1) 61 M[i][j] = M[i][j-1] * factor[i]; 62 } 63 } 64 65 int getVal(int x) { 66 int ret = 1, tmp; 67 68 for (int i=24; i>=0; --i) { 69 tmp = M[i][x&mask[i]]; 70 ret = ret * tmp % mod; 71 x >>= width[i]; 72 } 73 74 return ret; 75 } 76 77 ui32 calc(int x) { 78 ui32 ret = 0, tmp; 79 80 rep(i, 0, 25) { 81 ret <<= width[i]; 82 tmp = 0; 83 if (x%factor[i] == 0) { 84 while (x%factor[i] == 0) { 85 ++tmp; 86 x /= factor[i]; 87 } 88 } 89 ret += tmp; 90 } 91 92 return ret; 93 } 94 95 ui32 mymax(ui32 x, ui32 y) { 96 ui32 ret = max(x&0x70000000, y&0x70000000)\ 97 | max(x&0x0e000000, y&0x0e000000)\ 98 | max(x&0x01800000, y&0x01800000)\ 99 | max(x&0x00600000, y&0x00600000)\100 | ((x&0x001fffff) | (y&0x001fffff));101 return ret;102 }103 104 ui32 mymin(ui32 x, ui32 y) {105 ui32 ret = min(x&0x70000000, y&0x70000000)\106 | min(x&0x0e000000, y&0x0e000000)\107 | min(x&0x01800000, y&0x01800000)\108 | min(x&0x00600000, y&0x00600000)\109 | ((x&0x001fffff) & (y&0x001fffff));110 return ret;111 }112 113 inline void PushUp(int rt) {114 int lb = rt << 1;115 int rb = lb | 1;116 117 nd[rt].mx = mymax(nd[lb].mx, nd[rb].mx);118 nd[rt].mn = mymin(nd[lb].mn, nd[rb].mn);119 }120 121 void Build(int l, int r, int rt) {122 if (l == r) {123 int x;124 scanf("%d", &x);125 nd[rt].mx = nd[rt].mn = calc(x);126 return ;127 }128 129 int mid = (l + r) >> 1;130 131 Build(lson);132 Build(rson);133 PushUp(rt);134 }135 136 ui32 Query_mx(int l, int r, int rt) {137 if (L<=l && R>=r) {138 return nd[rt].mx;139 }140 141 int mid = (l + r) >> 1;142 ui32 ret;143 144 if (R <= mid) {145 ret = Query_mx(lson);146 } else if (L > mid) {147 ret = Query_mx(rson);148 } else {149 ui32 ltmp = Query_mx(lson);150 ui32 rtmp = Query_mx(rson);151 ret = mymax(ltmp, rtmp);152 }153 154 return ret;155 }156 157 ui32 Query_mn(int l, int r, int rt) {158 if (L<=l && R>=r) {159 return nd[rt].mn;160 }161 162 int mid = (l + r) >> 1;163 ui32 ret;164 165 if (R <= mid) {166 ret = Query_mn(lson);167 } else if (L > mid) {168 ret = Query_mn(rson);169 } else {170 ui32 ltmp = Query_mn(lson);171 ui32 rtmp = Query_mn(rson);172 ret = mymin(ltmp, rtmp);173 }174 175 return ret;176 }177 178 void Update(int k, int x, int l, int r, int rt) {179 if (l == r) {180 nd[rt].mx = nd[rt].mn = calc(x);181 return ;182 }183 184 int mid = (l + r) >> 1;185 186 if (k <= mid)187 Update(k, x, lson);188 else189 Update(k, x, rson);190 191 PushUp(rt);192 }193 194 int main() {195 ios::sync_with_stdio(false);196 #ifndef ONLINE_JUDGE197 freopen("data.in", "r", stdin);198 freopen("data.out", "w", stdout);199 #endif200 201 int n, q;202 char op[10];203 int tmp, k;204 int ans;205 206 init();207 while (scanf("%d %d", &n, &q) != EOF) {208 Build(1, n, 1);209 while (q--) {210 scanf("%s", op);211 if (op[0] == 'L') {212 scanf("%d %d %d", &L, &R, &mod);213 tmp = Query_mx(1, n, 1);214 ans = getVal(tmp);215 printf("%d\n", ans);216 } else if (op[0] == 'G') {217 scanf("%d %d %d", &L, &R, &mod);218 tmp = Query_mn(1, n, 1);219 ans = getVal(tmp);220 printf("%d\n", ans);221 } else {222 scanf("%d %d", &k, &tmp);223 Update(k, tmp, 1, n, 1);224 }225 }226 }227 228 #ifndef ONLINE_JUDGE229 printf("time = %d.\n", (int)clock());230 #endif231 232 return 0;233 }
转载于:https://www.cnblogs.com/bombe1013/p/5080288.html