{"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#define ull unsigned long long \nusing Misaka Mikoto;\nnamespace READ\n{\n\tull Read()\n\t{\n\t\tchar ch=getchar();\n\t\tull s=0;\n\t\twhile(ch<'0'||ch>'9') ch=getchar();\n\t\twhile(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();\n\t\treturn s;\n\t}\n\tull tp[10005];\n\tint l,r;\n\tull g1,g2;\n\tvoid init(int &n)\n\t{\n\t\tint i,k;\n\t\tn=Read(),k=Read(),l=1;\n\t\tfor(i=1;i<=k;i++)\n\t\t\ttp[i]=Read();\n\t}\n\tull read()\n\t{\n\t\tif(l>r)\n\t\t\tl=Read(),r=Read(),g1=Read(),g2=Read();\n\t\treturn tp[l++]*g1+g2;\n\t}\n}\nint main()\n{\n\tint n;\n   \tREAD::init(n);\n}\n```\n\n初始调用一次 `READ::init(n)`，之后你应调用 $n$ 次 `READ::read()`，第 $i$ 次 `READ::read` 返回 $a_i$。\n\n## Output\n\n一个整数，表示答案。答案对 $2^{64}$ 取模。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jswrnw5w.png)\n\n这个题本来是要拿到 Tree Diagram 上算的，但是 Tree Diagram 被某组织的宇宙射线射爆了，所以这个问题交给了你。\n\n不过你不需要计算出可能出现的最坏情况，只需要解决原问题就可以了。\n\n## Note\n\n保证读入模板消耗的时间少于 200ms，空间少于 1MB。\n\n### 数据规模\n\n本题采用捆绑测试。\n\n| $\\text{Subtask}$ | $n\\le$ | $\\text{Score}$ |\n| :----------: | :----------: | :----------: | \n| $1$ | $10^4$ | $10$ |\n| $2$ | $3\\times 10^6$ | $20$ |\n| $3$ | $4\\times 10^7$ | $30$ |\n| $4$ | $5\\times 10^7$ | $40$ |\n\n对于 $100\\%$ 的数据，$1\\le n\\le 5\\times 10^7$，$0\\le a_i <2^{64}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8569","tags":["2022","洛谷原创","O2优化","分治","位运算"],"sample_group":[["10 10\n2 8 9 1 9 2 7 1 2 10\n1 10 1 1","544"]],"created_at":"2026-03-03 11:09:25"}}