很明显的线段树，果然比用伸展树舒服多了，没有太多的思路，就是区间成段的更新 还有 区间 求和操作，直接看代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; // typedef struct { int l,r; ll sum; ll add; }Node; int n,m; ll num[200000 + 5]; Node tree[200005 * 2]; ll build(int root,int left,int right) { int mid; ll x,y; tree[root].l = left; tree[root].r = right; tree[root].add = 0; if(left == right) { tree[root].sum = num[left]; return num[left]; } mid = (left + right)/2; x = build(root * 2,left,mid); y = build(root * 2 + 1,mid + 1,right); return tree[root].sum = x + y; } void insert(int root,int left,int right,int add) { if(left <= tree[root].l && tree[root].r <= right) { tree[root].add += add; tree[root].sum += add*(tree[root].r - tree[root].l + 1); return ; } if(tree[root].add) { tree[root * 2].sum += tree[root].add * (tree[root * 2].r - tree[root * 2].l + 1); tree[root * 2 + 1].sum += tree[root].add * (tree[root * 2 + 1].r - tree[root * 2 + 1].l + 1); tree[root * 2 ].add += tree[root].add; tree[root * 2 + 1].add += tree[root].add; tree[root].add = 0; } if(left <= (tree[root].l + tree[root].r)/2) insert(root * 2,left,right,add); if(right > (tree[root].l + tree[root].r)/2) insert(root * 2 + 1,left,right,add); tree[root].sum = tree[root * 2].sum + tree[root * 2 + 1].sum; } ll find(int root,int left,int right) { ll x = 0,y = 0; if(left <= tree[root].l && tree[root].r <= right) return tree[root].sum; if(tree[root].add) { tree[root * 2].sum += tree[root].add * (tree[root * 2].r -tree[root * 2].l + 1); tree[root * 2 + 1].sum += tree[root].add * (tree[root * 2 + 1].r - tree[root * 2 + 1].l + 1); tree[root * 2 ].add += tree[root].add; tree[root * 2 + 1].add += tree[root].add; tree[root].add = 0; } if(left <= (tree[root].l + tree[root].r)/2) x = find(root * 2,left,right); if(right > (tree[root].l + tree[root].r)/2) y = find(root * 2 + 1,left,right); return x + y; } int main() { char s[2]; int a,b,c; while(scanf("%d %d",&n,&m) == 2) { for(int i=1;i<=n;i++) scanf("%I64d",&num[i]); build(1,1,n); for(int i=0;i b) { int tmp = a; a = b; b = tmp; } insert(1,a,b,c); } else { scanf("%d %d",&a,&b); if(a > b){ int tmp = a; a = b; b = tmp; } printf("%I64d\n",find(1,a,b)); } } } return EXIT_SUCCESS; }