[JRKSJ R6] 第七学区

Luogu

IDLGP8569

Time2077ms

Memory27MB

DifficultyP6

2022洛谷原创O2优化分治位运算

给你一个长度为 $n$ 的序列 $a$，求其所有子区间的按位或和的和。 ## Input **本题采用特殊的读入方式。以下是[读入模板](https://www.luogu.com.cn/paste/rz2t978c)：** ```cpp #include<bits/stdc++.h> #define Misaka namespace #define Mikoto std #define ull unsigned long long using Misaka Mikoto; namespace READ { ull Read() { char ch=getchar(); ull s=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s; } ull tp[10005]; int l,r; ull g1,g2; void init(int &n) { int i,k; n=Read(),k=Read(),l=1; for(i=1;i<=k;i++) tp[i]=Read(); } ull read() { if(l>r) l=Read(),r=Read(),g1=Read(),g2=Read(); return tp[l++]*g1+g2; } } int main() { int n; READ::init(n); } ``` 初始调用一次 `READ::init(n)`，之后你应调用 $n$ 次 `READ::read()`，第 $i$ 次 `READ::read` 返回 $a_i$。 ## Output 一个整数，表示答案。答案对 $2^{64}$ 取模。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/jswrnw5w.png) 这个题本来是要拿到 Tree Diagram 上算的，但是 Tree Diagram 被某组织的宇宙射线射爆了，所以这个问题交给了你。不过你不需要计算出可能出现的最坏情况，只需要解决原问题就可以了。 ## Note 保证读入模板消耗的时间少于 200ms，空间少于 1MB。 ### 数据规模本题采用捆绑测试。 | $\text{Subtask}$ | $n\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $10^4$ | $10$ | | $2$ | $3\times 10^6$ | $20$ | | $3$ | $4\times 10^7$ | $30$ | | $4$ | $5\times 10^7$ | $40$ | 对于 $100\%$ 的数据，$1\le n\le 5\times 10^7$，$0\le a_i <2^{64}$。

Samples

Input #1

10 10
2 8 9 1 9 2 7 1 2 10
1 10 1 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[JRKSJ R6] 第七学区",
    "description": {
      "content": "给你一个长度为 $n$ 的序列 $a$，求其所有子区间的按位或和的和。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2077,
      "memory_limit": 27648
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8569"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个长度为 $n$ 的序列 $a$，求其所有子区间的按位或和的和。\n\n## Input\n\n**本题采用特殊的读入方式。以下是[读入模板](https://www.luogu.com.cn/paste/rz2t978c)：**\n\n```cpp\n#include<bits/stdc++.h>\n#define Misaka namespace  \n#define Mikoto std \n#defin...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments